[ 백준 / C++ ] 2660 : 회장뽑기

[ 문제 ]

 

2660번: 회장뽑기

 

[ 접근방법 ]

 

회원 점수는 다른 회원과의 최단 거리 중 최댓값을 의미한다.

 

플로이드-워셜 알고리즘을 활용하여 각 회원 사이의 최단 거리를 모두 계산하고,

이를 토대로 회장 후보를 구하였다.

 

n이 최대 50이므로 O(n³) ≈ 125000 으로 충분하다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 100;
int n, dist[55][55], minScore = INF;
vector<int> candidates;

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

    cin >> n;
    for(int i = 1; i <= n; i++){
        fill(dist[i], dist[i] + n + 1, INF);
        dist[i][i] = 0;
    }

    while(1){
        int a, b;
        cin >> a >> b;
        if(a < 0)break;
        dist[a][b] = dist[b][a] = 1;
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    for(int i = 1; i <= n; i++){
        int maxDist = 0;
        for(int j = 1; j <= n; j++){
            if(i != j){
                maxDist = max(maxDist, dist[i][j]);
            }
        }

        if(maxDist < minScore){
            minScore = maxDist;
            candidates.clear();
            candidates.push_back(i);
        }
        else if(maxDist == minScore){
            candidates.push_back(i);
        }
    }

    cout << minScore << " " << candidates.size() << "\n";
    for(int candidate : candidates)cout << candidate << " ";

    return 0;
}