[백준/파이썬] 4485번

📍백준 4485번 문제

https://www.acmicpc.net/problem/4485

코드

import sys
import heapq

input = sys.stdin.readline

INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1


def dijkstra():
    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))
    distance[0][0] = 0
    while q:
        dist, x, y = heapq.heappop(q)
        if x == n-1 and y == n-1:
            print(f'Problem {cnt}: {distance[x][y]}')
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                ndist = dist + graph[nx][ny]
                if ndist < distance[nx][ny]:
                    distance[nx][ny] = ndist
                    heapq.heappush(q, (ndist, nx, ny))


while True:
    n = int(input())
    if n == 0:
        break
    graph = []
    for i in range(n):
        temp = list(map(int, input().split()))
        graph.append(temp)
    distance = [[INF] * n for _ in range(n)]

    dijkstra()
    cnt += 1

    # print(graph)

풀이

다익스트라를 이용하여 풀면 된다.