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

알고리즘 분류 : 다익스트라  

링크가 검은 루피를 먹으면서 루피를 잃으면서 이동할 때, 가장 적게 잃는 경로를 구하는 문제다. 각 칸마다 잃을 수 있는 루피는 0~9 이므로, 다익스트라 알고리즘을 통해 구현하면 된다.

• N X N 의 맵을 입력받고, 이를 dist 배열을 업데이트할 때 이용한다.
• 정답은 dist[n-1][n-1]에 있으며, 이 값에 처음부터 잃는 루피인 a[0][0]을 더해주어야 한다.
• 테스트케이스가 여러 개 주어지므로, 테스트케이스마다 dist 배열을 초기화해주어야 한다.

---

C++ 소스코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct zelda {
    // The person wearing green clothes is Zelda, right? No.. He is Link.
    int x, y, d;
    bool operator < (const zelda link) const { return d > link.d; }
};

int n;
int a[125][125];
int dist[125][125];
const int INF = 1e9;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dijkstra() {
    priority_queue<zelda> pq;
    pq.push({0, 0, 0});
    fill(&dist[0][0], &dist[n][0], INF);
    dist[0][0] = 0;
    while (!pq.empty()) {
        int x = pq.top().x, y = pq.top().y, d = pq.top().d;
        pq.pop();
        if (dist[x][y] < d) continue;
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            int nd = d + a[nx][ny];
            if (dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                pq.push({nx, ny, nd});
            }
        }
    }
    return dist[n-1][n-1] + a[0][0];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for (int t=1 ;; t++) {
        cin >> n;
        if (n == 0) break;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                cin >> a[i][j];
            }
        }
        cout << "Problem " << t << ": " << dijkstra() << '\n';
    }
    return 0;
}

---

Python 3 소스코드

from heapq import heappush, heappop
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

t = 0
INF = 1e9
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def dijkstra(n, a, dist):
    pq = []
    heappush(pq, (0, 0, 0))
    dist[0][0] = 0
    while pq:
        d, x, y = heappop(pq)
        if dist[x][y] < d:
            continue
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            nd = d + a[nx][ny]
            if dist[nx][ny] > nd:
                dist[nx][ny] = nd
                heappush(pq, (nd, nx, ny))
    return dist[n-1][n-1] + a[0][0]

while True:
    t += 1
    n = int(input())
    if n is 0:
        break
    a = [list(map(int, input().split())) for _ in range(n)]
    dist = [[INF]*n for _ in range(n)]
    print("Problem %d: %d\n" % (t, dijkstra(n, a, dist)))

---

참고

• 백준 온라인 저지 : BOJ 4485
• 최단경로