백준 4485번 C++ 풀이

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

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 4

문제

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

---

젤다... 아니 링크가 동굴을 빠져나올때, 최소한의 돈을 잃어야 하기 때문에(그러니까 도둑 루피의 개수가 최소가 되어야 하기 때문에) 이 문제는 최단거리 문제가 된다. 다만 이번 문제는 인접 행렬로 푸는게 그래프를 구성하는데 있어서 더 쉬울 것 같았다.

 

이번 문제를 풀면서 참 뭣같았던게, 지금까지 잘만 사용하던 다익스트라알고리즘 코드가 잘못되었다는 것이다(솔직히 아직도 왜 그것 때문에 틀린건지 모르겠다...).

 

사건의 발단은, 잘만 쓰던 다익스트라 코드를 가져다가 문제를 풀이하는 도중, 거리를 저장하는 dist변수를 어떻게 선언하는지에 따라 값이 천차만별로 바뀌었기 때문이다. 총 세개의 방법이었는데, N이 최대 125이기 때문에, 그냥 int dist[125][125]로 선언하는 경우, 백준의 채점서버에서는 VLA(가변 길이 배열)의 사용을 허가하기 때문에(gcc를 사용해서 그런듯 하다) int dist[n][n]으로 선언하는 경우, 그리고 std::vector를 사용해서 vector<vector<int>> dist(n, vector<int>(n, INF))로 선언한 경우 모두 예제을 입력했을때 출력이 달랐다. 알고리즘 코드는 수정도 하지 않고, 오로지 dist의 타입만 바꿨는데도....

 

결과값이 다 달랐다... 이게 맞나

 

정말 많이 억울한 심정에, 오픈채팅방에 아는 지인(?)에게 질문했고, 그 과정에서 그냥 내가 다익스트라를 지금까지 잘못 썼다는 것을 알게 되었다. 그리고 이 글들을 통해 내 다익스트라 코드를 점검했다.(사실 베꼈다고 하는게 맞겠..)

 

https://justicehui.github.io/medium-algorithm/2018/03/28/Dijkstra/

[그래프] 다익스트라 알고리즘

https://www.secmem.org/blog/2019/01/09/wrong-dijkstra/

잘못 구현한 다익스트라 알고리즘 저격하기

 

내가 틀렸던 코드, 그리고 정답 코드이다. 나와 비슷하게 고통을 받고 있거나, 또는 다익스트라를 공부하는 사람들에게 도움이 조금 되었으면 좋겠다.

 

// int dist[125][125]가 그나마 예제코드를 통과했었기 때문에 제출해봤다.
// + 잘못 쓰고 있던 다익스트라 코드는 덤
// 50%에서 "틀렸습니다" 나옴
#include <bits/stdc++.h>
#define endl '\n'
#define INF (int)1e9
using namespace std;
using tii = tuple<int, int, int>;

int n;
vector<vector<int>> graph;

void input() {
    graph.clear();
    graph.resize(n);
    for(auto& row : graph) {
        row.resize(n);
        for(auto& x : row) cin >> x;
    }
}

int sol() {
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    priority_queue<tii, vector<tii>, greater<tii>> pq;
    int dist[125][125]; fill(&dist[0][0], &dist[124][124], INF); 
    bool visited[n][n] = {false,};

    dist[0][0] = graph[0][0];
    pq.push(tii(dist[0][0], 0, 0)); // 거리, x, y
    while(!pq.empty()) {
        auto [cur_dist, cur_x, cur_y] = pq.top();
        pq.pop();
        if (visited[cur_y][cur_x]) continue;

        visited[cur_y][cur_x] = true;
        for(int i = 0; i < 4; i++) {
            int next_x = cur_x + dx[i], next_y = cur_y + dy[i];
            if (next_x >= n || next_x < 0 || next_y >= n || next_y < 0) continue;
            if (dist[next_y][next_x] > dist[cur_y][cur_x] + graph[next_y][next_x]) {
                dist[next_y][next_x] = dist[cur_y][cur_x] + graph[next_y][next_x];
                pq.push(tii(dist[next_y][next_x], next_x, next_y));
            }
        }
    }
    return dist[n - 1][n - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i = 1; ; i++) {
        cin >> n;
        if(!n) break;
        input();
        cout << "Problem " << i << ": " << sol() << endl;
    }
}

 

// 정답 코드
// 다익스트라 코드를 점검하고나니, dist의 타입이 뭐든간에 모두 같은 답이 나왔다.
#include <bits/stdc++.h>
#define endl '\n'
#define INF (int)1e9
using namespace std;
using tii = tuple<int, int, int>; // 순서대로 거리, x, y

int n;
vector<vector<int>> graph;

void input() {
    graph.clear();
    graph.resize(n);
    for(auto& row : graph) {
        row.resize(n);
        for(auto& x : row) cin >> x;
    }
}

int sol() {
    priority_queue<tii, vector<tii>, greater<tii>> pq;
    int dx[4] = {1, 0, -1, 0}; // 동, 남, 서, 북
    int dy[4] = {0, 1, 0, -1};
    vector<vector<int>> dist(n, vector<int>(n, INF));
    
    dist[0][0] = graph[0][0];
    pq.push({dist[0][0], 0, 0});

    while(!pq.empty()) {
        auto[cur_dist, cur_x, cur_y] = pq.top();
        pq.pop();

        if (cur_dist > dist[cur_y][cur_x]) continue;

        for(int i = 0; i < 4; i++) {
            int next_x = cur_x + dx[i];
            int next_y = cur_y + dy[i];
            if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= n) continue;

            int next_dist = cur_dist + graph[next_y][next_x];
            if(dist[next_y][next_x] > next_dist) {
                dist[next_y][next_x] = next_dist;
                pq.push({next_dist, next_x, next_y});
            }

        }
    }
    return dist[n - 1][n - 1];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i = 1; ; i++) {
        cin >> n;
        if(!n) break;
        input();
        cout << "Problem " << i << ": " << sol() << endl;
    }
}

 

"틀렸습니다" = 틀린 코드 / "맞았습니다!!" = 정답 코드 / 런타임 에러 = 정답코드 완성전 작은 실수