[BOJ / C++] 가운데에서 만나기 (골드4 - 플로이드)

문제링크: https://www.acmicpc.net/problem/21940

 

1. 코드

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

const int INF = (INT_MAX / 2) - 1;

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> d(n+1, vector<int>(n+1, INF));
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int a, b, time;
        cin >> a >> b >> time;

        d[a][b] = min(d[a][b], time);
    }

    int k;
    cin >> k;

    vector<int> cityList(k);
    for (int i = 0; i < k; i++) {
        cin >> cityList[i];
    }

    for (int p = 1; p <= n; p++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][p] + d[p][j] < d[i][j]) {
                    d[i][j] = d[i][p] + d[p][j];
                }
            }
        }
    }

    vector<int> candidateList;

    int minTime = INF;
    for (int candidate = 1; candidate <= n; candidate++) {
        int maxTime = 0; 
        for (int city : cityList) {
            int time = 0;
            time += d[city][candidate];
            time += d[candidate][city];

            maxTime = max(time, maxTime);
        }
        
        if (maxTime < minTime) {
            candidateList.clear();
            candidateList.push_back(candidate);

            minTime = maxTime;
        }
        else if (maxTime == minTime) {
            candidateList.push_back(candidate);
        }
    }

    sort(candidateList.begin(), candidateList.end());
    for (int c : candidateList) {
        cout << c << ' ';
    }
}

 

 

2. 시간복잡도

• 도시 개수 n이 200이므로 O(n^3)도 풀이 가능하고, 플로이드 워셜 알고리즘을 적용한다.
• 3중 for문을 통해 d 테이블을 업데이트하는데 가장 높은 시간복잡도가 걸리고, 200^3 = 8,000,000 < 10^8 이므로 시간제한 1초 내에 통과 가능하다.

 

3. 분석

 

문제 설명이 이해하기 좀 어렵다. (계속 읽다보면 의도는 알겠는데 한번에 이해하기 어려웠다.) 주요 조건을 분석하면 다음과 같다.

• 각 친구들은 서로 다른 도시에 산다.
• A → B, B → A 시간은 다를 수 있다.
• 각 도시 1~N 중 하나의 약속 장소 X를 정할 것이다.
• 각 친구들이 사는 지역에서 X까지 왕복하는데 걸리는 시간이 있을 것이다.
• 각 친구들이 사는 지역에서 X까지 왕복하는데 걸리는 시간들 중 최댓값을 구하면, 그 최댓값은 약속 장소를 X로 정했을 때 왕복시간의 최댓값이 된다.
• 1~N 중 어떤 장소를 약속장소 X로 정해야 왕복시간 최댓값이 최소가 되는가?  

문제에서 최대가 최소가 된다는 표현이 무슨말인지 처음에 헷갈렸는데 이런 뜻 이었다. 

 

약속장소 X는 TC에서 확인할 수 있듯이 친구들이 사는 지역도 가능하다.

이때 자기자신으로의 왕복시간은 0이 된다.

 

d 테이블을 채우는 것까지는 플로이드 알고리즘과 똑같고 핵심은 Line 43 부터이다.

후보도시는 1~N까지 순회하면서 각 X에 대한 왕복시간중 최댓값을 구해낸다.

이후 그 최댓값이 기존까지의 최소왕복시간보다 작으면 후보리스트를 초기화하고 담는다.

기존 최소왕복시간과 같다면 후보리스트에 추가한다. 큰 경우는 관심 밖이므로 무시한다.

 

이런식으로 후보 X를 골라내면 된다.