백준 21278번 호석이 두 마리 치킨

문제 요약

정점 수가 $N$이고, 간선 수가 $M$인 무방향 그래프가 주어진다. 모든 간선의 길이는 1이다.

다음과 같은 값이 최소가 되는 정점 $u, v$의 번호를 오름차순으로 출력하고 그 값을 출력해야 한다. 같은 값을 가지는 정점 쌍이 여러개라면 사전순으로 제일 앞서게 출력하면 된다.
$$
2\sum_{t \in V}min(dist(u, t), dist(v, t))
$$
$N \le 100, N-1 \le M \le N(N-1)/2$

실제로 문제에서 식을 주진 않았는데 이를 잘 해석하면 위 식의 값을 구하는 것이 맞다.

풀이

일단 모든 정점에서부터 모든 정점으로까지의 최단 거리를 구해야 한다. 이를 위해서 플로이드 워셜을 사용할 수도 있지만 그래프가 무방향에다 모든 간선의 가중치가 동일하므로 BFS를 사용해도 무방하다.

따라서 모든 정점에서부터 모든 간선으로 까지의 최단거리를 $O(N(N+M))$만에 구할 수 있다.

이 값을 구했으면 모든 정점 쌍에 대하여 주어진 식의 값을 구한 뒤에 최솟값을 찾으면 된다.

모든 정점 쌍은 $O(N^2)$만큼 있으며, 위 식의 값을 구하는 데에는 $O(N)$만큼 걸리므로 총 $O(N^3)$이 걸린다.

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
vector<vector<int>> G(105);
int dist[105][105];
int N, M;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=0;i<M;++i) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(dist, -1, sizeof(dist));
    for(int i=1;i<=N;++i) {
        queue<int> q;
        q.push(i);
        dist[i][i] = 0;
        while(!q.empty()) {
            int cur = q.front();
            int d = dist[i][cur];
            q.pop();
            for(int nxt : G[cur]) {
                if(dist[i][nxt] != -1) continue;
                dist[i][nxt] = d + 1;
                q.push(nxt);
            }
        }
    }
    pair<int, pair<int,int>> ans = {INF, {INF, INF}};
    for(int i=1;i<=N;++i) {
        for(int j=1;j<=N;++j) {
            int sum = 0;
            for(int k=1;k<=N;++k) sum += 2*min(dist[i][k], dist[j][k]);
            ans = min(ans, make_pair(sum, make_pair(i, j)));
        }
    }
    cout << ans.second.first << ' ' << ans.second.second << ' ' << ans.first << '\n';
    return 0;
}