[파이썬 | SW Expert Academy] 최소합

[문제]

 

그림처럼 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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

[풀이]

 

좌측 상단에서 우측 하단으로 이동하는 경우만 생각하므로, 오른쪽 혹은 아래로 이동하는 것을 고려한다.

따라서 오른쪽 혹은 아래로만 이동하면, 방문 했던 곳에 또 방문하는 경우는 없으므로, check list를 만들어서 visited를 검사할 필요가 없다.

 

따라서 nextI, nextJ가 주어진 범위 [0, N)에만 존재하는지만 검사하면 된다.

 

그 후 현재 방문 노드가 마지막 우측 하단이면, 지금까지 최소값과 비교해서 바꾼다.

 

 

T = int(input())
d = [[0, 1], [1, 0]]
 
def DFS(i, j, s, depth):
    global ans
    s += maps[i][j]
    if depth == 2*N-1:
        if ans > s:
            ans = s
        return 
 
    for idx in range(2):
        nextI, nextJ = i + d[idx][0], j + d[idx][1]
        if nextI < N and nextJ < N:
            DFS(nextI, nextJ, s, depth+1)
    
 
for t in range(1, T+1):
    N = int(input())
    ans = 99999999
    maps = []
    for i in range(N):
        maps.append(list(map(int, input().split())))
    DFS(0, 0, 0, 1)
    print('#%d %d' % (t, ans) )

하지만 이 경우 최종적으로 시간 초과 판정을 받게 된다.

 

따라서, DFS를 진행하면서 s값이 지금까지 구한 ans값보다 커지면 return 하도록 코드를 수정했다.

 

 

T = int(input())
d = [[0, 1], [1, 0]]
 
def DFS(i, j, s):
    global ans
    s += maps[i][j]
    if s > ans:
        return
    if i == N-1 and j == N-1:
        ans = s
        return 
 
    for idx in range(2):
        nextI, nextJ = i + d[idx][0], j + d[idx][1]
        if nextI < N and nextJ < N:
            DFS(nextI, nextJ, s)
    
 
for t in range(1, T+1):
    N = int(input())
    ans = 99999999
    maps = []
    for i in range(N):
        maps.append(list(map(int, input().split())))
    DFS(0, 0, 0)
    print('#%d %d' % (t, ans) )

위의 최종 코드로 통과할 수 있다.