[BOJ/C++] 녹색 옷 입은 애가 젤다지?(4485번)

1. 개요

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

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

1-1. 설명

젤다의 전설 시리즈 주인공, 링크는 도둑 루피만 가득한 N x N 크기 동굴의 제일 위쪽에 있다. 젤다는 어떠한 이유로 인해 동굴안쪽까지 들어와버렸다. 그래서 제일 오른쪽 아래인 출구로 이동해야 하는 상황이다. 각 칸마다 도둑루피가 존재하는데, 이 칸을 지나면 해당 도둑루피 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 해 동굴 건너편까지 이동해야 하고, 한 번에 상하좌우 인접한 곳으로 한칸씩 이동할 수 있다. 링크가 잃을 수 밖에 없는 최소 금액은 얼마인지 구하는 프로그램을 작성한다.

1-2. 제한 사항

 - 입력은 여러 개 테스트 케이스로 이루어져 있음

 - 각 테스트 케이스 첫 줄에는 동굴 크기를 나타내는 정수 N이 주어지며, N은 2 이상 125 이하

 - N이 0으로 들어오면 전체 입력이 종료됨

 - 이어서 N개 줄에 걸쳐 동굴 각 칸에 있는 도둑 루피 크기가 공백으로 구분되어 차례대로 주어짐

 - 모든 정수는 0 이상 9 이하 한자리 수

---

2. 구현

2-1. 풀이

최소 금액이므로, 가중치가 최대한 작은 경로로 이동해야 한다. 다익스트라 알고리즘을 이용하였으며, 2차원 배열이므로 x, y 좌표와 각 루피의 비용을 구조체로 저장하여 다익스트라 알고리즘을 적용하였다. 

2-2. 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

constexpr size_t INF = 99999999;

struct Node {
    int x;
    int y;
    int cost;
};

int map[125][125];
int dist[125][125];

int dirX[4] = { 0, 0, 1, -1 };
int dirY[4] = { 1, -1, 0, 0 };

int N;

void dijkstra(int startX, int startY);
struct compare { // 구조체 우선순위 큐를 위한 compare 함수
    bool operator() (const Node& node1, const Node& node2) {
        return node1.cost > node2.cost;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int index = 1;
    while (true) {
        cin >> N;
        if (N == 0) break;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
        fill(&dist[0][0], &dist[124][125], INF);
        dijkstra(0, 0);
        cout << "Problem " << index++ << ": " << dist[N - 1][N - 1] << "\n";
    }

    return 0;
}

void dijkstra(int startX, int startY) {
    priority_queue<Node, vector<Node>, compare> queue; // 구조체 우선순위 큐
    queue.push({ startX, startY, map[startX][startY]}); // x, y 좌표와 가중치
    dist[startX][startY] = map[startX][startY]; // 시작 가중치

    while (!queue.empty()) {
        int nodeX = queue.top().x;
        int nodeY = queue.top().y;
        int cost = queue.top().cost;
        queue.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = nodeX + dirX[i];
            int nextY = nodeY + dirY[i];
            if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;

            int nextCost = map[nextX][nextY];

            int nextDist = cost + nextCost;
            if (dist[nextX][nextY] > nextDist) {
                dist[nextX][nextY] = nextDist;
                if (nextX == N - 1 && nextY == N - 1) break;
                queue.push({ nextX, nextY, dist[nextX][nextY] });
            }
        }
    }
}