[ 백준 6118 ] 숨바꼭질 (C++)

백준의 숨바꼭질(6118) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾아야 하는 문제이다.

1번 헛간에서 멀어지면 멀어질수록 발냄새가 감소한다고 했으므로, 1번 정점을 기준으로 가장 먼 거리에 있는 헛간을

구해주면 된다.

본인은 이 과정에서 다익스트라 알고리즘을 사용해 주었다.

다익스트라 알고리즘을 진행할 때, 거리가 기존의 최장 경로와 비교했을 때, 더 거리가 먼 정점이 발생하면,

이 정점을 벡터에 넣어주었다.

왜냐하면, 최장 경로가 같은 헛간이 여러개 존재할 수 있기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
#define endl "\n"
#define MAX 20010
#define INF 987654321
using namespace std;
 
int N, M, Answer;
int Dist[MAX];
vector<int> V[MAX];
vector<int> Answer_V;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) Dist[i] = INF;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
}
 
void Solution()
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, 1));
    Dist[1] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i];
            int nCost = Cost + 1;
            
            if (Dist[Next] > nCost)
            {
                Dist[Next] = nCost;
                PQ.push(make_pair(-nCost, Next));
 
                if (Dist[Next] > Answer)
                {
                    Answer = Dist[Next];
                    Answer_V.clear();
                    Answer_V.push_back(Next);
                }
                else if (Dist[Next] == Answer) Answer_V.push_back(Next);
            }
        }
    }
 
    sort(Answer_V.begin(), Answer_V.end());
    cout << Answer_V[0] << " " << Answer << " " << Answer_V.size() << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}