SWEA-1249-보급로

매트릭스가 주어지고 시작지점(0, 0)과 도착지점(N-1, N-1)이 주어진다.
그 외의 매트릭스 값은 0~9 사이의 값이며 이 값은 해당 지점까지 가는 데 필요한 비용이다.
출발지점에서 도착지점까지 갈 수 있는 경로중 이 비용의 최소값을 구하는 문제

• BFS+델타탐색을 통해 출발지점에서 도착지점까지 완전탐색
• 완전탐색에 걸리는 시간을 줄이기 위해 Memoization을 사용

from collections import deque

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

def BFS():
    queue = deque()
    queue.append([0, 0])

    while queue:
        r, c = queue.popleft()
        for i in range(4):
            dr, dc = r + dx[i], c + dy[i]
            if 0 <= dr < N and 0 <= dc < N and V[dr][dc] > V[r][c] + M[dr][dc]: # Memoization으로 쓸데없는 탐색 줄임
                V[dr][dc] = V[r][c] + M[dr][dc]
                queue.append([dr, dc])

    return V[N-1][N-1]


for T in range(1, int(input()) + 1):
    N = int(input())
    M = [list(map(int, input())) for _ in range(N)]
    V = [[100001 for _ in range(N)] for _ in range(N)] # Memoization
    V[0][0] = 0
    result = BFS()
    print('#{} {}'.format(T, result))