백준 21940번: 가운데에서 만나기 (C++)

문제링크

https://www.acmicpc.net/problem/21940

풀이방법

해당 문제는 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다.

• 플로이드 알고리즘을 통해서 각 노드 사이의 최단 거리를 계산 해 놓는다.
• 우선순위 큐를 활용하여 <세 친구의 왕복 시간 중 가장 큰 값, 도시 번호>를 넣어서 왕복 시간이 가장 적은 도시를 바로 꺼낼 수 있게 만든다.
• 왕복 시간이 가장 작은 것이 가장 위쪽에 존재하므로 우선 해당하는 도시의 번호를 출력한다. 왕복 시간이 가장 작은 것이 여러 개라면 해당 도시 번호까지 전부 출력한다.

위 설명의 시퀀스를 이해하고 아래 코드를 참고하자.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b, c, k, num, ans_min;
vector<int> friends;
const int INF = 0x3f3f3f3f;
int d[1005][1005];

priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> >
pq;
//  <세 친구의 왕복 시간 중 가장 큰 값, 도시 번호>

int main()
{
    cin >> n >> m;
    
    //우선 플로이드 알고리즘을 통해서 각 도시와 도시 사이의 최소시간을 미리 구한다.
    for (int i = 1; i <= n; i++) fill(d[i], d[i] + (n + 1), INF);
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b],c);
        //nxt[a][b] = b;
    }
    for (int i = 1; i <= n; i++) d[i][i] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                if (d[j][k] > d[j][i] + d[i][k])
                {
                    d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
                    //nxt[j][k] = nxt[j][i];
                }
            }
        }
    }

    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> num;
        friends.push_back(num);
    }

    // 친구들의 i도시 까지 왕복 시간중 가장 큰 값들만 pq에 넣는다.
    for (int i = 1; i <= n; i++)
    {
        int max_fr = 0;
        for (auto nxt : friends)
        {
            //if (i == nxt) continue;
            if(max_fr < d[nxt][i] + d[i][nxt])
            max_fr = d[nxt][i] + d[i][nxt];
        }
        pq.push({ max_fr, i});
    }
    
    // 왕복 시간이 가장 작은것이 가장 위쪽에 존재하므로 우선 해당하는 도시의 번호를 출력한다.
    pair<int, int> ans_min = pq.top();
    pq.pop();
    cout << ans_min.second << ' ';

    // 다음 위쪽에 있는 값이 처음 출력했던 왕복시간의 최솟값과 똑같으면 해당 도시의 번호도 출력한다.
    while (!pq.empty() && ans_min.first == pq.top().first)
    {
        ans_min = pq.top();
        pq.pop();
        cout << ans_min.second << ' ';
    }
    return 0;
}