백준 2660 플로이드 워셜 ) 골드5 - 회장뽑기

 

일단 문제를 무지성으로 빠르게 풀려고 최적화나 코드 가독성을 챙기지 못하였습니다. 

 

풀이: x와 y 친구관계를 입력받을때 짝사랑하는 친구가 아니니까 양방향 그래프로 dp[x][y], dp[y][x]를 1로 초기화합니다

그 다음 플로이드 워셜 알고리즘을 활용하여 친구들의 수를 세어줍니다 

 

그리고 i 번호의  j번째 친구들 중에 가장 큰 값을 i번호의 친구수로 지정합니당

 

그럼 score라는 벡터변수에 { 친구수 : 번호 } 이렇게 들어갑니다 그걸 오름차순 정렬을 해주고

 

제일 작은 친구들의 수를 가진 번호를 찾아 출력하면 간단하게 풀 수 있습니당!

 

아래는 코드입니다

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

using namespace std;

int main() {


    int n;

    cin >> n;
    vector<vector<long long>> dp(51, vector<long long>(51, 1000000000));


    while(true) {
        int x,y;

        cin >> x >> y;

        if(x == -1 && y == -1) break;

        dp[x][y] = 1;
        dp[y][x] = 1;
    }

    for(int i = 1; i <= 50; i++) {
        dp[i][i] = 0;
    }

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


    vector<pair<long long,long long>> score(n+1, pair<int,int>(0, 0));

    for(int i = 1; i <= n; i++) {
        score[i].second = i;
        for(int j = 1; j <= n; j++) {
            if(dp[i][j] == 1000000000) continue;
            score[i].first = max(score[i].first, dp[i][j]);
        }

    }

    sort(score.begin(), score.end());

    int end = score[1].first;

    vector<int> count;
    for(int i = 1; i <= score.size(); i++) {
        if(end != score[i].first) break;

        count.push_back(score[i].second);
    }

    cout << end << " " << count.size() << endl;

    for(auto i = 0; i < count.size(); i++) {
        cout <<  count[i] << " ";
    }

    return 0;
}