SWEA 5188 최소합 (python)

5188. [파이썬 S/W 문제해결 구현] 2일차 - 최소합 D3

문제

그림처럼 NxN 칸에 숫자가 적힌 판이 주어지고, 각 칸에서는 오른쪽이나 아래로만 이동할 수 있다.

맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가 얼마인지 출력하는 프로그램을 만드시오.

1	2	3
2	3	4
3	4	5

그림의 경우 1, 2, 3, 4, 5순으로 움직이고 최소합계는 15가 된다. 가능한 모든 경로에 대해 합을 계산한 다음 최소값을 찾아도 된다.

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 가로 세로 칸 수 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 10이하의 자연수가 주어진다. 3<=N<=13

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

풀이과정

맨처음에 dfs 를 이용하여 풀려다가 잘못풀었다.

import sys
sys.stdin = open("input.txt")

T = int(input())

def road(x, y):
    global temp, total
    if x == y == N-1:
        temp += arr[y][x]
        if temp < total:
            total = temp
            return
        else:
            return
    elif x > N-1 or y > N-1:
        return
    else:
        if not visited[y][x]:
            visited[y][x] = 1
            temp += arr[y][x]
            road(x+1, y)
            road(x, y+1)






for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int,input().split()))for _ in range(N)]
    temp = 0
    total = 10 * 2 * N
    visited = [[0 for _ in range(N)]for _ in range(N)]
    road(0, 0)


    print("#{} {}".format(tc, total))

import sys
sys.stdin = open("input.txt")

T = int(input())

def road(x, y, total):
    global result
    if x == N-1 and y == N-1:
        total += arr[y][x]
        if total < result:
            result = total
            return
    if total > result:
        return

    dx = [1, 0]
    dy = [0, 1]

    for i in range(2):
        x += dx[i]
        y += dy[i]
        if x > N-1 or y > N-1:
            continue
        if not visited[y][x]:
            visited[y][x] = 1
            road(cx, cy, total + arr[y][x])
            visited[y][x] = 0









for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int,input().split()))for _ in range(N)]
    temp = 0
    result = 10 * 2 * N
    visited = [[0 for _ in range(N)]for _ in range(N)]
    road(0, 0, 0)


    print("#{} {}".format(tc, result))

다음으로는 이렇게 풀었는데 x와 y를 설정해 주는 것이 틀렸다.

이상하게 나옴

풀이

T = int(input())

# 길찾기 dfs
def road(x, y, total):
    global result
    # 만약 도착했다면
    if x == N-1 and y == N-1:
        # 마지막 도착점것을 더해주고
        total += arr[y][x]
        # 최소값을 갱신해준다.
        if total < result:
            result = total
            return
    # 시간을 줄이기위해 과정중에 현재 최소값 보다 크면 계산 가치 x
    if total > result:
        return

    dx = [1, 0]
    dy = [0, 1]

    # 모드를 돌아다니면서 검색
    for i in range(2):
        # 다음 좌표 둘러보기
        cx = x + dx[i]
        cy = y + dy[i]
        # 만약 범위 넘어가면 패스
        if x > N-1 or y > N-1:
            continue
        # 방문한 적이 없다면
        if not visited[y][x]:
            # 방문도장 찍고
            visited[y][x] = 1
            # 다음 좌표 보면서 total 값도 같이 넘겨줌
            road(cx, cy, total + arr[y][x])
            # 돌아왔다면 방문도장 지워주기
            visited[y][x] = 0

for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int,input().split()))for _ in range(N)]
    # 결괏값은 최대값으로 설정
    result = 10 * 2 * N
    # 방문 검사를 위한 배열
    visited = [[0 for _ in range(N)]for _ in range(N)]
    # 길찾아보자 - 함수호출
    road(0, 0, 0)


    print("#{} {}".format(tc, result))