[백준 2660] 회장뽑기 (C++)

문제 링크: www.acmicpc.net/problem/2660

2660번: 회장뽑기

1. 주의할 점

- 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 플로이드 와샬 알고리즘(시간복잡도: O(N^3)로 50^3 < 10^9)을 사용하여 구한다

- 간선들의 정보를 입력 받기 전, Dist[][] 배열을 1000으로 초기화한다

- 간선들의 정보를 입력받은 후, 플로이드 와샬을 통해 I<->J 까지의 최소 간선 수를 구한다

- 1~N번까지의 사람들 중에서 가장 먼 사람과의 회장 후보 점수를 Temp에 저장하고 Result와 비교하여 V 벡터를 갱신한다

- 위의 과정을 모두 거친 후, V 벡터를 정렬하고 출력한다

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dist[51][51];
int num,a,b;

int main() {
    cin >>num;
    for(int i=1;i<=num;i++)
        for(int j=1;j<=num;j++){
            if(i==j) continue;
            else dist[i][j]=1000;
        }
    while(1){
        cin>>a>>b;
        if(a+b==-2) break;
        dist[a][b]=1;
        dist[b][a]=1;
    }
    for(int t=1;t<=num;t++)
        for(int i=1;i<=num;i++)
            for(int j=1;j<=num;j++)
                dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
    int result = 1000;
    vector<int> v;
    for(int i=1;i<=num;i++){
        int temp = 0;
        for(int j=1;j<=num;j++)
            temp=max(temp,dist[i][j]);
        if(temp<result){
            v.clear();
            result = temp;
            v.push_back(i);
        }
        else if(temp==result)
            v.push_back(i);
    }
    sort(v.begin(),v.end());
    cout << result << " "<<v.size()<<'\n';
    for(int i=0;i<v.size();i++)
        cout << v[i]<<" ";
    return 0;
}