# BOJ - 4485 - 녹색 옷 입은 애가 젤다지?

Updated:

```
import sys
from heapq import heappush, heappop
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
INF = 1e9
def Dijkstra(graph, N):
heap = []
distance = [[INF] * N for _ in range(N)]
heappush(heap, (graph[0][0], 0, 0))
distance[0][0] = 0
while heap:
weight, x, y = heappop(heap)
if x == N-1 and y == N-1:
return weight
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
w = weight + graph[nx][ny]
if w < distance[nx][ny]:
distance[nx][ny] = w
heappush(heap, (w, nx, ny))
def solution():
cnt = 1
while True:
N = int(input())
if N == 0:
break
graph = []
for _ in range(N):
graph.append(list(map(int, sys.stdin.readline().split())))
print("Problem {0}: {1}".format(
cnt, Dijkstra(graph, N)
))
cnt += 1
solution()
```

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

## Leave a comment