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

www.acmicpc.net/problem/4485

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

 

상하좌우 이동을 통해 각 칸으로 이동하면 해당 칸에 배정된 점수를 얻게된다.

이때 오른쪽 아래까지 이동하는동안 얻을 수 있는 최소 점수를 찾는 문제이다.

 

풀이

 노드와 간선이 안주어젔을뿐 전형적인 다익스트라 문제이다.

#include<iostream>
#include<queue>
 
#define INF 2100000000
 
using namespace std;
 
int board[150][150];
int dist[150][150];
int N;
 
int moveX[4] = { 1,0,-1,0 };
int moveY[4] = { 0,1,0,-1 };
 
class Node {
public:
    int x, y, score;
    Node(int x_, int y_, int score_) : x(x_), y(y_), score(score_) {}
    Node() : Node(-1,-1,-1) {}
    bool operator<(const Node& rhs) const {
        return score > rhs.score;
    }
};
 
int Dijkstra() {
    priority_queue<Node> pq;
    pq.push(Node(0, 0, board[0][0]));
    dist[0][0] = 0;
    int ret = INF;
    while (!pq.empty()) {
        Node cNode = pq.top();
        pq.pop();
 
        int nx, ny;
        for (int dir = 0; dir < 4; dir++) {
            nx = cNode.x + moveX[dir];
            ny = cNode.y + moveY[dir];
            
            if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                continue;
 
            if (dist[ny][nx] > cNode.score + board[ny][nx]) {
                dist[ny][nx] = cNode.score + board[ny][nx];
                pq.push(Node(nx, ny, dist[ny][nx]));
            }
        }
    }
    return dist[N - 1][N - 1];
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testcase = 1;
    while (1) {
        cin >> N;
        if (N == 0)
            break;
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                cin >> board[row][col];
                dist[row][col] = INF;
            }
        }
 
        int val = Dijkstra();
        cout << "Problem " << testcase << ": " << val << "\n";
 
        testcase++;
    }
 
    return 0;
}