[백준] 4485_녹색 옷 입은 애가 젤다지? C++

26 Nov 2023 in Study on Coding Test

다익스트라 알고리즘 문제

정답제출코드

#include <iostream>
#include <vector>
#include <queue>

#define MAX 99999999

using namespace std;

typedef pair<int, pair<int, int>> piii;

int N;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<vector<int>> Map;
vector<vector<int>> Accul;

int Dijkstra()
{
    priority_queue<piii> pq;
    pq.push({-Map[0][0], {0, 0}});
    Accul[0][0] = Map[0][0];

    while (!pq.empty())
    {
        int CurX = pq.top().second.first;
        int CurY = pq.top().second.second;
        int CurCost = -pq.top().first;
        pq.pop();

        if (Accul[CurY][CurX] < CurCost)
            continue;
        
        for (int i = 0; i < 4; ++i)
        {
            int Nx = CurX + dx[i];
            int Ny = CurY + dy[i];

            if (!(0 <= Nx && Nx < N && 0 <= Ny && Ny < N))
                continue;
            
            int NextCost = CurCost + Map[Ny][Nx];
            if (Accul[Ny][Nx] > NextCost)
            {
                Accul[Ny][Nx] = NextCost;
                pq.push({-NextCost, {Nx, Ny}});
            }
        }
    }

    return Accul[N-1][N-1];
}

void Init()
{
    cin >> N;

    if (N == 0)
        exit(0);

    Map.clear();
    Accul.clear();
    for (int i = 0; i < N; ++i)
    {
        vector<int> row;
        vector<int> Accul_Row;
        for (int j = 0; j < N; ++j)
        {
            int _input;
            cin >> _input;
            row.push_back(_input);
            Accul_Row.push_back(MAX);
        }
        Map.push_back(row);
        Accul.push_back(Accul_Row);
    }
}

void Solution(int n)
{
    cout << "Problem "<< n << ": " << Dijkstra() << '\n';
}

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

    int cnt = 1;
    while (true)
    {
        Init();
        Solution(cnt);
        cnt++;
    }

    return 0;
}

격자맵에 다익스트라 알고리즘을 사용하면 되는 문제였다.

다만 고민했던 부분이 간선이 아니라 노드를 지날 때 마다 값을 포함하기 때문에

어떻게 값을 계산할까 고민했었다.

그리고 답은 간단했다.

시작할 때 우선순위 큐에 넣을 때 값을 이렇게 넣어주는 것이다.

priority_queue<piii> pq;
pq.push({-Map[0][0], {0, 0}});
Accul[0][0] = Map[0][0];

여기서 주의할 점은, -Map[0][0]으로 넣어줘야 한다.

왜냐하면 우선순위 큐는 특정하게 값을 설정하지 않는 이상 높은 값을 우선순위에 둔다.

즉, 최대 힙인 것이다.

높은 값 부터 탐색할 수 있도록, 2, 4, 6, 8..이 있다면 -2, -4, -6, -8 등 높은 값부터 탐색하도록 한 것이다.

그래서 값을 꺼내고 넣을 때 아래와 같이 코드를 작성하는데

int CurX = pq.top().second.first;
int CurY = pq.top().second.second;
int CurCost = -pq.top().first;

...

pq.push({-NextCost, {Nx, Ny}});

Map[0][0]을 그대로 넣어버리면 다음 값을 계산할 때 오류가 나는 것이다.

여기서 해맸었다.