BOJ #2660 - 회장뽑기

https://icpc.me/2660

# 문제 분류
최단 경로 찾기 (Floyd-Warshall Algorithm)

풀이 접근 방법 :

 

1. 일단 최단 경로 찾는 알고리즘을 사용해야 한다.

2. 각각의 노드 별로 최단 경로를 계산해야 하므로, Floyd-Warshall 알고리즘이 적합하다. (input size도 고려해서)

→ Bellman-Ford와 Dijkstra, SPFA 모두 단일 시작점 s에 관해 다른 정점 v에 이르는 최단경로를 찾는 알고리즘이다.

3. Floyd-Warshall 이후, 한 노드(후보)로부터 다른 각각의 노드로 가는 최소 가중치 값 중 최대가 해당 후보의 점수이다.

4. 그 점수가 가장 작은 사람을 회장으로 세우면 된다.

 

---

https://koosaga.com/2 구사과님 포스트의 '으히'님의 댓글을 보면 알겠지만,

Bellman-Ford와 Dijkstra, SPFA를 사용하여 각각의 후보마다 한번씩, 즉 n번 돌려주면 모든 노드에 대해서 가능하긴 하다.

그래도 간선의 수가 가장 많은 경우(Worst case)에는 Floyd-Warshall이 가장 빠르다는 것 같기도,,,

input size가 넉넉하니까 Floyd-Warshall을 쓰자 ㅋ ㅋ

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
 
 
using namespace std;
 
int INF = 10000000;
int N, a, b, minscore[51], res = INF, cnt;
int adj[51][51];
bool flag;
 
int main(){
    scanf("%d", &N);
    for(int i=0; i<51; i++){
        for(int j=0; j<51; j++){
            adj[i][j] = INF;
            adj[j][j] = 0;
        }
    }
 
    while(1){
        scanf("%d %d", &a, &b);
        if(a == -1 && b == -1) break;
        else{
            adj[a][b] = 1;
            adj[b][a] = 1;
            minscore[a] = 1;
            minscore[b] = 1;
        }
    }
 
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            for(int k=1; k<=N; k++){
                if(adj[j][k] > adj[j][i] + adj[i][k]){
                    adj[j][k] = adj[j][i] + adj[i][k];
                }
            }
        }
    }
 
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(adj[i][j] == INF) continue;
            minscore[i] = max(minscore[i], adj[i][j]);
        }
    }
 
    for(int i=1; i<=N; i++){
        if(minscore[i] == 0) flag = true;
        res = min(res, minscore[i]);
    }
 
    for(int i=1; i<=N; i++){
        if(minscore[i] == res){
            cnt++;
        }
    }
 
    if(flag){
        res = 0;
        cnt = 0;
    }
 
    printf("%d %d\n", res, cnt);
 
    for(int i=1; i<=N; i++){
        if(minscore[i] == res){
            printf("%d ", i);
        }
    }
 
    return 0;
}