[Python/파이썬] SW Expert Academy 1249번 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

 

코드

from heapq import heappop, heappush

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

for tc in range(1, int(input())+1):
    n = int(input())
    board = [input() for _ in range(n)]

    t = [[int(1e9)]*n for _ in range(n)]
    t[0][0] = 0
    t[0][1] = int(board[0][1])
    t[1][0] = int(board[1][0])

    hq = []
    heappush(hq, (t[0][1], 0, 1))
    heappush(hq, (t[1][0], 1, 0))
    while hq:
        cost, x, y = heappop(hq)
        if x == n-1 and y == n-1:
            break
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < n and 0 <= ny < n and t[nx][ny] > t[x][y] + int(board[nx][ny]):
                t[nx][ny] = t[x][y] + int(board[nx][ny])
                heappush(hq, (t[nx][ny], nx, ny))
    print(f"#{tc} {t[n-1][n-1]}")

 

출발점인 (0, 0)에서 (N-1, N-1)까지 가는 경로 중 가장 짧은 경로를 찾기 위해 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘인 다익스트라 알고리즘을 사용했다. 찾은 최단 경로는 t라는 2차원 배열에 저장한다.