[백준] 1238번_파티 C++

04 Apr 2023 in Study on Coding Test

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

정답제출코드

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

#define INF 99999999

using namespace std;

struct Vill
{
    int num;
    int acculdist;
    // 왼쪽 : 번호 , 오른쪽 : 거리
    vector<pair<int, int>> link;

    Vill(int _num) : num(_num), acculdist(INF){};
};

int N, M, X;
vector<Vill> Vills;

void DistSet()
{
    for (size_t i = 0; i < Vills.size(); ++i)
    {
        Vills[i].acculdist = INF;
    }
    return;
}

int dijkstra(int start, int end)
{
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));

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

        if (Dist > Vills[Cur].acculdist)
            continue;

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

            if (Vills[Next].acculdist > Dist + DistToNext)
            {
                Vills[Next].acculdist = Dist + DistToNext;
                pq.push(make_pair(-Vills[Next].acculdist, Next));
            }
        }
    }

    return Vills[end].acculdist;
}

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

    cin >> N >> M >> X;
    
    Vill padding(0);
    Vills.push_back(padding);

    for (int i = 1; i <= N; ++i)
    {
        Vill v(i);
        Vills.push_back(v);
    }

    for (int i = 0; i < M; ++i)
    {
        int s, e, d;
        cin >> s >> e >> d;

        Vills[s].link.push_back(make_pair(e, d));
    }

    int ans = 0;

    for (int i = 1; i <= N; ++i)
    {
        if (i == X)
            continue;

        DistSet();
        int Go = dijkstra(i, X);
        DistSet();
        int Come = dijkstra(X, i);
        
        if (ans < Go + Come)
            ans = Go + Come;
    }

    cout << ans;

    return 0;
}

다익스트라 알고리즘을 이용해서 풀 수 있었다.

각각의 개인마다

갈 때 다익스트라 알고리즘을 한번, 올 때 다익스트라 알고리즘을 한 번 사용해서

개인 별 왕복시간을 구할 수 있었다.

int ans = 0;

    for (int i = 1; i <= N; ++i)
    {
        if (i == X)
            continue;

        DistSet();
        int Go = dijkstra(i, X);
        DistSet();
        int Come = dijkstra(X, i);
        
        if (ans < Go + Come)
            ans = Go + Come;
    }

    cout << ans;

이 때, 다익스트라 알고리즘을 실행하기 전에 초기화를 해주기 위해서 DistSet함수를 만들었고,

구성은 아래와 같다.

void DistSet()
{
    for (size_t i = 0; i < Vills.size(); ++i)
    {
        Vills[i].acculdist = INF;
    }
    return;
}

이렇게 해서 왕복의 길이가 가장 큰 경우의 값을 출력하도록 구현하였다.

다익스트라 알고리즘은 우선순위 큐를 이용해서 구현하였다.

각 마을이 모두 연결되어있는 데이터가 제공된다고 했으니 안심하고

곧바로 End 지점까지의 누적 거리를 반환하도록 하였다.