백준 4485 녹색 옷 입은 애가 젤다지? (C++)

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

그래프 탐색을 이용한 문제이다. 이 문제는 bfs와 다익스트라 두 방식으로 해결할 수 있다. 사실상 우선순위 큐를 사용했냐 안했냐 차이이다. 우선순위 큐를 이용한 다익스트라 쪽이 시간이 거의 1/2 일 정도로 더 빠르다. 지나온 값들의 합을 배열에 저장해주어 이를 비교하며 최솟값을 구해 다시 저장해주며 이를 반복하여 값을 구해주었다. 아래에 두 방식의 코드가 있다. 굉장히 시간이 오래 걸린 문제였다... 어려워서가 아니라 이상한 곳에서 메모리 초과가 났었다. 이유는 아래와 같다.

// 기존 코드
if (d[ny][nx] < cost + A[ny][nx]) continue;

// 새로운 코드
if (d[ny][nx] <= cost + A[ny][nx]) continue;

코드를 고쳐봤더니 바로 통과하였다.... 같을 경우를 고려하지 않아 큐에 많은 불필요한 데이터가 추가되었고 이로인해 메모리 초과가 발생했던 것이다... 너무 초보적인 실수라 어이가 없었다. 두번다시는 이런 실수는 일어나지 않도록 집중해서 문제를 풀도록 하자.

---

bfs 코드

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

using namespace std;

int N;
int A[126][126];
int dp[126][126];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

void bfs() {
    queue<pair<int, int>> q;

    dp[1][1] = A[1][1];
    q.push({ 1,1 });

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny<1 || nx<1 || ny>N || nx>N) continue;
            if (dp[y][x] + A[ny][nx] >= dp[ny][nx]) continue;

            dp[ny][nx] = dp[y][x] + A[ny][nx];
            q.push({ ny,nx });
        }
    }
}

void solution(int problem) {
    bfs();
    cout << "Problem " << problem << ": " << dp[N][N] << "\n";
}

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

    int i = 1;
    while (1) {
        cin >> N;
        if (!N) break;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cin >> A[i][j];
                dp[i][j] = 987654321;
            }
        }

        solution(i++);
    }

    return 0;
}

다익스트라 코드

#include <iostream>
#include <queue>

using namespace std;

int N;
int A[125][125];
int d[125][125];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

void dijstra() {
    priority_queue<pair<int, pair<int, int>>> pq;

    pq.push({ -A[0][0],{0,0} });
    d[0][0] = A[0][0];

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int y = pq.top().second.first;
        int x = pq.top().second.second;

        pq.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (d[ny][nx] <= cost + A[ny][nx]) continue;

            d[ny][nx] = cost + A[ny][nx];
            pq.push({ -d[ny][nx],{ny,nx} });
        }
    }
}

void solution(int problem) {
    dijstra();
    cout << "Problem " << problem << ": " << d[N-1][N-1] << "\n";
}

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

    int i = 1;
    while (1) {
        cin >> N;
        if (!N) break;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> A[i][j];
                d[i][j] = 987654321;
            }
        }

        solution(i++);
    }

    return 0;
}