백준 2660 회장뽑기 - C++, 플로이드-와샬

2660번: 회장뽑기

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, score, num, minnium;
int vote[51][51];
int result[51];

int main(){

    scanf("%d", &n);

    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            vote[i][j] = 999999999;
        }
    }

    while(true){
        int from, to;
        scanf("%d %d", &from, &to);

        if(from == -1 || to == -1)
            break;

        vote[from][to] = 1;
        vote[to][from] = 1;
    }
    
    for(int via = 1; via <= n; via++){
        for(int to = 1; to <= n; to++){
            for(int from = 1; from <= n; from++){
                vote[from][to] = min(vote[from][to], vote[from][via] + vote[via][to]);
            }
        }
    }

    minnium = 10000;

    for(int i = 1; i <= n; i++){
        result[i] = 0;
        for(int j = 1; j <= n; j++){
            if(i == j)
                continue;
            result[i] = max(result[i], vote[i][j]);
        }
        minnium = min(result[i], minnium);
        score = minnium;
    }

    num = 0;
    vector<int> v;
    for(int i = 1; i <= n; i++){
        if(result[i] == score){
            v.push_back(i);
            num++;
        }
    }

    printf("%d %d\n", score, num);
    for(int i = 0; i < num; i++)
        printf("%d ", v[i]);

}   

---

 좀 너무 무지성으로 짠 코드가 아닌가 했지만 테스트 케이스가 50개라 무지성으로 해도 좋을 것 같습니다.

 

1. 입력 (양방향)

2. 플로이드-와샬 알고리즘으로 친구 관계를 업데이트 해줍니다.

3. 각 배열을 보면서 제일 작은 점수를 선정해냅니다. 동시에 친구 관계 결과값중 제일 큰 값을 업데이트 해줍니다.

4. 업데이트된 1차원 배열을 모두 탐색하면서 제일 작은 점수의 사람들을 세고 저장합니다.