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

이번 문제는  맨 왼쪽 위에서 맨 오른쪽 아래까지 이동할 때의 숫자 합계의 최솟값을 구하는 문제이다.

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    min_sum = float('inf')
    
    def dfs(x, y, total):
        global min_sum
        if total >= min_sum:     # 이미 최소합보다 크면 가지치기
            return
        # 도착지점에 도달했을 때
        if x == N-1 and y == N-1:
            min_sum = min(min_sum, total)
            return
        
        for dx, dy in [(1, 0), (0, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N:
                dfs(nx, ny, total+arr[nx][ny])
    
    dfs(0, 0, arr[0][0])
            
    print(f"#{test_case} {min_sum}")

난 DFS로 풀려고 했는데 중간부터 잘 안 돼서 인터넷 검색해서 풀었다... 분발하자...

 

+) 다음 날 다시 풀었을 때 풀이: