[백준] 4485번-(Python 파이썬) - Dijkstra

문제링크 : https://www.acmicpc.net/problem/4485

이번 문제는 (0,0)부터 (n-1,n-1)까지 찾아갈 때 가중치를 가장 적게 찾아가는 문제이다.
다른 bfs,dfs문제를 많이 풀어보고 이 문제를 풀어보는게 좋을 것 같다.

heapq를 이용하여 bfs알고리즘을 구현하고, 조건에 맞게 반복문을 구현해주면 간단하게 해결 가능하다.

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize

cnt = 1

def dijkstra():
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    
    heap = []
    dp = [[inf] * n for _ in range(n)]
    dp[0][0] = maze[0][0]
    visit = [[0] * n for _ in range(n)]
    visit[0][0] = 1

    heappush(heap, [maze[0][0], 0, 0])
    while heap:
        c, x, y = heappop(heap)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
                dp[nx][ny] = min(dp[nx][ny], dp[x][y] + maze[nx][ny])
                heappush(heap, [dp[nx][ny], nx, ny])
                visit[nx][ny] = 1
    return dp[n-1][n-1]

while True:
    n = int(input())
    if n == 0:
        break
    maze = []
    for _ in range(n):
        maze.append(list(map(int, input().split())))
    ans = dijkstra()
    print(f"Problem {cnt}: {ans}")
    cnt += 1