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

문제 링크: https://www.acmicpc.net/problem/4485

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

<문제 풀이> 다익스트라 알고리즘

 

다익스트라 알고리즘으로 출발점에서 도착점까지 최단 경로를 구하면 됩니다.

 

<C++소스코드>

 

#include<iostream>
#include<queue>
#include<functional>
#include<cstring>
#include<utility>
#include<tuple>
using namespace std;

const int MAX_N = 125;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };

int board[MAX_N][MAX_N];
int d[MAX_N][MAX_N];
int n;

bool OOB(int x, int y) {
    return (x < 0 || y < 0 || x >= n || y >= n);
}

int dijkstra(int sx, int sy) {
    memset(d, 0x3f, sizeof(d));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;
    d[sx][sy] = board[sx][sy];
    pq.push({ d[sx][sy], sx, sy });
    while (!pq.empty()) {
        int cx, cy, cur_dist; tie(cur_dist, cx, cy) = pq.top(); pq.pop();
        if (d[cx][cy] != cur_dist) continue;

        for (int dir = 0; dir < 4; dir++) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];
            if (OOB(nx, ny)) continue;
            int nxt_dist = cur_dist + board[nx][ny];
            if (nxt_dist < d[nx][ny]) {
                d[nx][ny] = nxt_dist;
                pq.push({nxt_dist, nx, ny });
            }
        }
    }
    return d[n - 1][n - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int test_case = 0;
    while (true) {
        test_case++;
        cin >> n;
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> board[i][j];
            }
        }
        cout << "Problem " << test_case << ": " << dijkstra(0, 0) << '\n';
    }


    return 0;
}