[SWEA] 1249. [S/W 문제해결 응용] 4일차 - 보급로

1249. [S/W 문제해결 응용] 4일차 - 보급로

문제 풀이

• 다익스트라 알고리즘 사용

from collections import deque
INF = 1e6

t = int(input())

for c in range(1, 11):

    n = int(input())
    arr = [list(map(int, input())) for _ in range(n)]
    distance = [[INF] * n for _ in range(n)]

    q = deque()
    q.append([0, 0])
    distance[0][0] = 0

    def bfs():
        while q:
            a, b = q.popleft()

            dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
            for i in range(4):

                nx = a + dx[i]
                ny = b + dy[i]

                if 0 <= nx < n and 0 <= ny < n:

                    if distance[nx][ny] > distance[a][b] + arr[nx][ny]:
                    	# 더 작은 값으로 교체
                        distance[nx][ny] = distance[a][b] + arr[nx][ny]  
                        q.append([nx, ny])

    bfs()
    print(f"#{c} {distance[-1][-1]}")