[백준] 9370_미확인 도착지 C++

25 Sep 2023 in Study on Coding Test

다익스트라 알고리즘을 활용해보는 문제

메모리 관리가 중요했었다.

정답제출코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>

#define INF 99999999
#define MAX 2001

using namespace std;

vector<pair<int, int>> link[MAX];
int N, M, C;
int S, G, H;

vector<int> Candidates;
int result1[MAX];
int result_g[MAX];
int result_h[MAX];
int Dest_GH;

void Fill(int* result)
{
    for (int i = 1; i <= 2000; ++i)
        result[i] = INF;
}

void Dijkstra(int start, int* result)
{
    for (int i = 1; i <= N; ++i)
        result[i] = INF;

    priority_queue<pair<int, int>> pq;
    pq.push({ 0, start });
    result[start] = 0;

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

        if (CurCost > result[Cur])
            continue;

        for (size_t i = 0; i < link[Cur].size(); ++i)
        {
            int Next = link[Cur][i].second;
            int NextCost = link[Cur][i].first + CurCost;

            if (NextCost < result[Next])
            {
                result[Next] = NextCost;
                pq.push({ -NextCost, Next });
            }
        }
    }
}

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

    int TC;
    cin >> TC;

    for (int k = 0; k < TC; ++k)
    {
        Fill(result1);
        Fill(result_g);
        Fill(result_h);

        for (int i = 1; i <= 2000; ++i)
            link[i].clear();

        Candidates.clear();
        cin >> N >> M >> C;
        cin >> S >> G >> H;

        for (int i = 0; i < M; ++i)
        {
            int s, e, c;
            cin >> s >> e >> c;
            link[s].push_back({c, e});
            link[e].push_back({c, s});
        }

        for (int i = 0; i < C; ++i)
        {
            int a;
            cin >> a;

            Candidates.push_back(a);
        }

        sort(Candidates.begin(), Candidates.end());

        Dijkstra(S, result1);
        Dijkstra(G, result_g);
        Dest_GH = result_g[H];
        Dijkstra(H, result_h);

        for (size_t i = 0; i < Candidates.size(); ++i)
        {
            int Can = Candidates[i];
            if (result1[Can] == result1[G] + Dest_GH + result_h[Can] || 
                result1[Can] == result1[H] + Dest_GH + result_g[Can])
                cout << Can << ' ';
        }
        cout << '\n';
    }
    return 0;
}

오답제출코드(메모리초과)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>

#define INF 99999999

using namespace std;

struct Node
{
    vector<pair<int, int>> link;
    int acculCost = INF;
};

int N, M, C;
int S, G, H;
vector<Node> Cities;
vector<int> RouteSelect;
vector<int> RealRoute;
vector<int> Candidates;

bool IsHere(int a, int b)
{
    bool flag1 = false;
    bool flag2 = false;
    for (size_t i = 0; i < RealRoute.size(); ++i)
    {
        if (RealRoute[i] == a)
            flag1 = true;
        if (RealRoute[i] == b)
            flag2 = true;

        if (flag1 && flag2)
            return true;
    }

    return false;
}

int Dijkstra(int start, int end)
{
    priority_queue<pair<int, int>> pq;
    pq.push({ 0, start });
    Cities[start].acculCost = 0;

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

        if (CurCost > Cities[Cur].acculCost)
            continue;

        for (size_t i = 0; i < Cities[Cur].link.size(); ++i)
        {
            int Next = Cities[Cur].link[i].second;
            int NextCost = Cities[Cur].link[i].first + CurCost;

            if (NextCost <= Cities[Next].acculCost)
            {
                RouteSelect[Next] = Cur;
                Cities[Next].acculCost = NextCost;
                pq.push({ -NextCost, Next });
            }
        }
    }

    return Cities[end].acculCost;
}

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

    int TC;
    cin >> TC;

    for (int k = 0; k < TC; ++k)
    {
        Cities.clear();
        RouteSelect.clear();
        Candidates.clear();
        cin >> N >> M >> C;
        cin >> S >> G >> H;

        for (int i = 0; i <= N; ++i)
        {
            Node n;
            Cities.push_back(n);

            int RouteNum = 0;
            RouteSelect.push_back(RouteNum);
        }

        for (int i = 0; i < M; ++i)
        {
            int s, e, c;
            cin >> s >> e >> c;
            Cities[s].link.push_back({c, e});
            Cities[e].link.push_back({c, s});
        }

        for (int i = 0; i < C; ++i)
        {
            int a;
            cin >> a;
            
            RealRoute.clear();

            for (int j = 0; j <= N; ++j)
                RouteSelect[j] = 0;

            for (int j = 0; j <= N; ++j)
                Cities[j].acculCost = INF;

            int MaxCost = Dijkstra(S, a);

            RealRoute.push_back(a);
            int idx = RouteSelect[a];

            while (idx != S)
            {
                RealRoute.push_back(idx);
                idx = RouteSelect[idx];
            }
            RealRoute.push_back(S);

            if (IsHere(G, H))
                Candidates.push_back(a);
        }

        sort(Candidates.begin(), Candidates.end());

        for (size_t i = 0; i < Candidates.size(); ++i)
            cout << Candidates[i] << ' ';
        cout << '\n';
    }
    return 0;
}

다익스트라 알고리즘을 이용해 목적지 까지 최단 경로를 산출하고,

경로 상에 목적지가 있는지를 파악하는 로직으로 풀었다.

for (int i = 0; i < C; ++i)
{
    int a;
    cin >> a;
    
    RealRoute.clear();

    for (int j = 0; j <= N; ++j)
        RouteSelect[j] = 0;

    for (int j = 0; j <= N; ++j)
        Cities[j].acculCost = INF;

    int MaxCost = Dijkstra(S, a);

    RealRoute.push_back(a);
    int idx = RouteSelect[a];

    while (idx != S)
    {
        RealRoute.push_back(idx);
        idx = RouteSelect[idx];
    }
    RealRoute.push_back(S);

    if (IsHere(G, H))
        Candidates.push_back(a);
}

여기서 말하는 RealRoute가 지나간 경로를 파악하는 벡터이다.

그리고 IsHere 함수를 통해서 경로상에 두 확정지(?)가 모두 있는지를 파악한다.

두 확정지, 즉 확실하게 지나갔다고 판단되는 노드가 모두 있다면

목적지로 가능한 후보지이므로 a를 Candidates에 넣어준다.

경로 역추적

생각해보면 경로를 어떻게 역추적해야하지?

궁금한 경우가 많다. 써먹을 일도 많고.

vector<int> RouteSelect;
vector<int> RealRoute;

...


int Dijkstra(int start, int end)
{
    priority_queue<pair<int, int>> pq;
    pq.push({ 0, start });
    Cities[start].acculCost = 0;

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

        if (CurCost > Cities[Cur].acculCost)
            continue;

        for (size_t i = 0; i < Cities[Cur].link.size(); ++i)
        {
            int Next = Cities[Cur].link[i].second;
            int NextCost = Cities[Cur].link[i].first + CurCost;

            if (NextCost <= Cities[Next].acculCost)
            {
                RouteSelect[Next] = Cur;
                Cities[Next].acculCost = NextCost;
                pq.push({ -NextCost, Next });
            }
        }
    }

    return Cities[end].acculCost;
}


...


RealRoute.push_back(a);
int idx = RouteSelect[a];

while (idx != S)
{
    RealRoute.push_back(idx);
    idx = RouteSelect[idx];
}
RealRoute.push_back(S);

어떻게 보면 우선순위 큐를 쓰는 다익스트라 알고리즘은

최단경로이자, 유일한 경로를 파악해주는 것이기 때문에

경로, 거리를 갱신하고 우선순위 큐에 다음 경로를 넣어주는 과정에서

Next입장에서 이전에 어느 쪽에서 왔었는지, 즉 Cur은 몇번인지를

배열에 저장해주면 된다.

그리고 도착지에서부터 저장한 배열을 통해 경로를 역추적하면서

스택에 순차적으로 저장하고, 스택에서 값을 빼내면서 역순으로 출력하면

그것이 시작점->도착점으로 가는 경로가 된다!

정답 코드로의 변환

그러나 결과는 메모리 초과였다.

도저히 원인을 모르겠어서 구글링을 통해 참고링크를 참조해보니

경로 상에 G와 H가 있는지 검증하는 방법이 달랐다.

나는 새로운 벡터를 이용해서 이전 경로를 저장한 다음 경로를 역추적하는 방법을 사용했는데

이 분들은 다익스트라 알고리즘을 여러번 돌려서 거리를 저장한다음 거리를 계산하는 방법을 사용하신 것이다.

아무래도 경로를 저장할 때 순환 경로가 발생해서 스택 오버플로우가 일어나는 것이 아닐까 생각이 들었다.

그리고 pq에 저장되는 노드의 수도 너무 많았던 것 같다.

for (size_t i = 0; i < link[Cur].size(); ++i)
{
    int Next = link[Cur][i].second;
    int NextCost = link[Cur][i].first + CurCost;

    if (NextCost <= result[Next])
    {
        result[Next] = NextCost;
        pq.push({ -NextCost, Next });
    }
}

이 부분에서

if (NextCost < result[Next])

등호를 없애주니 메모리 초과가 발생하지 않고 정답처리 되었다.

[백준] 9370_미확인 도착지 C++

정답제출코드

오답제출코드(메모리초과)

경로 역추적

정답 코드로의 변환

우키의 일지

Error

정답제출코드

오답제출코드(메모리초과)

경로 역추적

정답 코드로의 변환

Templates (for web app):

Error