[SWEA] 1249_보급로 (다익스트라 이용)

📕 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

💡 풀이법

1. 다익스트라 알고리즘을 이용했다.

2. dp 2차원 리스트에는 출발점에서 부터 그 위치까지 갈 때 드는 최단시간이 담기게 된다.

3. 현재 위치에서 사방을 탐색해서 갈 수 있는 곳이라면 다음 위치의 dp값과 (현재 위치의 dp값 + 다음 위치 복구시간)을 비교해서 다음 위치의 dp값이 더 크다면 다음 위치를 deq에 담고 다음 위치의 dp값을 (현재 위치의 dp값 + 다음위치복구시간)으로 갱신시켜 준다.

4. 그렇게 함수 실행이 끝나고 나면, dp의 도착지 위치에는 도착지까지 가는 최단 시간이 담기게 된다.

 

from collections import deque

def dijkstra(x,y):
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    deq = deque([(x, y)])
    dp[x][y] = 0

    while deq:
        x, y = deq.popleft()

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

            if -1 < nx < N and -1 < ny < N:
                if dp[nx][ny] > dp[x][y] + matrix[nx][ny]:
                    deq.append((nx, ny))
                    dp[nx][ny] = dp[x][y] + matrix[nx][ny]

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, list(input()))) for _ in range(N)]
    dp = [[float('inf') for _ in range(N)] for _ in range(N)]
    dijkstra(0,0)
    print('#{} {}'.format(tc, dp[N-1][N-1]))