[SWEA/Python] 1249. 보급로

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 다익스트라 알고리즘 사용
2. 출발지에서 인접한 위치를 탐색하며 원래 저장된 비용보다 현재 경로로 온 비용이 적다면 비용을 갱신하고,
   현재 위치를 큐에 넣는다.
3. 큐가 빌 때까지 2를 반복 후, 도착지에 저장된 비용을 출력한다.

 

📌 코드

from collections import deque
import sys
sys.stdin = open('input.txt')

def restore(i, j):
    queue = deque()
    queue.append((i, j))

    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while queue:
        x, y = queue.popleft()

        for dx, dy in dxy:
            nx, ny = x+dx, y+dy

            if 0 <= nx < N and 0 <= ny < N:
                if cost[x][y]+load[nx][ny] < cost[nx][ny]:
                    cost[nx][ny] = cost[x][y]+load[nx][ny]
                    queue.append((nx, ny))

            
T = int(input())

for t in range(1, T+1):
    N = int(input())
    load = []

    for _ in range(N):
        temp = []
        for n in input():
            temp.append(int(n))
        load.append(temp)
    
    cost = [[float('inf') for _ in range(N)] for _ in range(N)]

    cost[0][0] = load[0][0]
    restore(0, 0)

    print('#{} {}'.format(t, cost[N-1][N-1]))