[ 백준 4485 ] 녹색 옷 입은 애가 젤다지? (C++) - 다익스트라

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 문제를 보고 바로 다익스트라인 것을 알았다. (양수 가중치, 최단거리가 아닌 가장 비용이 낮은 거리)
2. 먼저 이동할 Map을 만드는데, 이동에 필요한 cost와 지금까지의 비용인 dist를 넣어주었다.
3. 나머지는 다익스트라 알고리즘에 맞게 dist가 갱신될 수 있을 때마다 갱신해주면서 넣어주었다.
4. 단, 0인 지점은 아직 방문한적이 없을 때, (dist == INF) 이동할 수 있게 하였고, 그 이후에는 3번과정을 반복했다.
5. 도착점의 dist를 출력하면 최소비용으로 가는 거리를 구할 수 있다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<queue>
#define INF 987654321

using namespace std;

struct Map
{
    int cost = 0;
    int dist = INF;
};

int N;
int next_x[] = { 1,-1,0,0 };
int next_y[] = { 0,0,1,-1 };
Map myMap[125][125];
void input() {
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            cin >> myMap[y][x].cost;
        }
    }
    myMap[0][0].dist = myMap[0][0].cost;
}

int sol() {
    queue<pair<int, int>> q;
    q.push({ 0,0 }); // x,y

    while (!q.empty()) {
        int cx = q.front().first, cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cx + next_x[i], ny = cy + next_y[i];
            int nextDist = myMap[ny][nx].dist, curDist = myMap[cy][cx].dist;
            int nextCost = myMap[ny][nx].cost, curCost = myMap[cy][cx].cost;
            if (nx > -1 && ny > -1 && nx < N && ny < N) {
                if (nextCost == 0 && nextDist == INF) {
                    q.push({ nx,ny });
                    myMap[ny][nx].dist = curDist;
                }
                //else if (nextCost == 0 && curDist < nextDist) {
                //    q.push({ nx,ny });
                //    myMap[ny][nx].dist = curDist;
                //}
                else {
                    if (nextDist > curDist + nextCost) {
                        q.push({ nx,ny });
                        myMap[ny][nx].dist = curDist + nextCost;
                    }
                }
            }
        }
    }
    return myMap[N - 1][N - 1].dist;
}

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

    int testcase = 1;
    while (1) {
        cin >> N;
        if (N == 0) return 0;
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                myMap[y][x].cost = 0;
                myMap[y][x].dist = INF;
            }
        }
        input();
        cout << "Problem " << testcase++ << ": " << sol() << endl;
    }

    return 0;
}

---

🤔 문제 후기

전형적인 다익스트라 문제로 풀 수 있지만, 비용이 0일 때, 무조건 가게 해준다면 무한 반복되서 메모리가 초과될 수 있다. 비용이 0인 지점에 대한 예외만 잘 설정할 수 있다면 다익스트라를 안다는 가정 하에 푸는데 문제는 없을 문제였다.