[백준] 4485번 녹색 옷 입은 애가 젤다지? 파이썬 코드

코드

# 처음 시작, 마지막 점 도착 => 한 점에서 다른 한 점으로의 최단거리
# 가중치는 0~9사이의 정수이므로 다익스트라 알고리즘 사용 가능
# 상하좌우 움직이는 경우를 파악해야 하므로 bfs 풀이 아이디어를 빌려온다.

from heapq import heappop, heappush
import sys
INF = 987654321
input = sys.stdin.readline
def dijkstra(first,x,y):
  dx,dy = [1,-1,0,0], [0,0,1,-1] # 상하좌우 움직일 경우의 수
  queue = [(first, x,y)] # 비용, 행, 열
  visited[x][y] = first
  while queue:
    now, popx,popy = heappop(queue)
    if now > visited[popx][popy]: continue # 계산할 필요 없는 값
    for i in range(4):
      nx = popx + dx[i]
      ny = popy + dy[i]
      if 0<=nx<n and 0<=ny<n:
        cost = now + graph[nx][ny]
        if visited[nx][ny] > cost:
          visited[nx][ny] = cost
          heappush(queue, (cost, nx, ny))    
cnt = 1
while 1:
  n = int(input())
  if n == 0: break
  graph = [[*map(int, input().split())] for _ in range(n)]
  visited = [[INF]*(n) for _ in range(n)]
  dijkstra(graph[0][0],0,0)
  print(f'Problem {cnt}: {visited[n-1][n-1]}')
  cnt += 1