[Baekjoon] 4485. 녹색 옷 입은 애가 젤다지?

🔗 Problem Link

4485번: 녹색 옷 입은 애가 젤다지?

---

❔Thinking

• NxN 크기의 공간이 주어질 때, (0,0)에서 출발해 (N-1, N-1)로 이동하는 최소 비용을 반환한다.

---

💻Solution

import heapq

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

def dijkstra(x, y, graph):
    q = []
    n = len(graph)
    heapq.heappush(q, (graph[x][y], x, y))
    while q:
        dist, x, y = heapq.heappop(q)
        if distance[x][y] < dist:
            continue
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0<=nx<n and 0<=ny<n:
                cost = dist + graph[nx][ny]
                if cost < distance[nx][ny]:
                    distance[nx][ny] = cost
                    heapq.heappush(q, (cost, nx, ny))


T = 1
while True:
    x, y = 0, 0
    n = int(input())
    if n == 0:
        break
    graph = []
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    distance = [[INF] * n for _ in range(n)]
    distance[x][y] = graph[x][y]
    dijkstra(x, y, graph)
    print(f'Problem {T}: {distance[n-1][n-1]}')
    T += 1

---

🗝️keypoint

1. 특정 위치에서 다른 특정한 위치로의 최소비용은 Dijkstra 알고리즘을 활용한다. 
2. 다른 위치로의 이동은 0,0을 항상 지나치기 때문에, 0,0을 지나치는 비용도 더해야 한다.