백준 4485. 녹색 옷 입은 애가 젤다지?

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

1. 큐 풀이

from collections import deque
import sys
input = sys.stdin.readline

cnt = 0

while True:
    n = int(input())
    if n == 0:
        break
    cnt += 1

    arr = [list(map(int,input().split())) for _ in range(n)]
    dp = [[float('inf') for _ in range(n)] for _ in range(n)]
    dp[0][0] = arr[0][0] # 시작점 설정 꼭 해주기!!

    q = deque([[0,0]])

    while q:
        i, j = q.popleft()
        for di, dj in [[0,1],[0,-1],[-1,0],[1,0]]:
            ni, nj = i+di, j+dj
            if 0 <= ni < n and 0 <= nj < n:
                new_cost = dp[i][j] + arr[ni][nj]
                if new_cost < dp[ni][nj]:  # 더 적은 비용이면 갱신
                    dp[ni][nj] = new_cost
                    q.append([ni, nj])  # 갱신된 경우에만 큐에 추가

    print(f"Problem {cnt}: {dp[n - 1][n - 1]}")

2. 힙 풀이(훨씬 빠름!)

import heapq
import sys
input = sys.stdin.readline

cnt = 0
inf = int(1e9)

while True:
    n = int(input())

    if n == 0:
        break

    cnt += 1
    arr = [list(map(int,input().split())) for _ in range(n)]
    q = []
    v = [[inf] * n for _ in range(n)]
    v[0][0] = 0
    heapq.heappush(q,(arr[0][0],0,0))

    while q:
        c, i, j = heapq.heappop(q)
        for ti, tj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + ti, j + tj
            if 0 <= ni < n and 0 <= nj < n:
                cost = c + arr[ni][nj]
                if v[ni][nj] > cost:
                    v[ni][nj] = cost
                    heapq.heappush(q,(cost,ni, nj))

    print(f'Problem {cnt}: {v[n-1][n-1]}')