2610 회의준비

문제 링크

https://www.acmicpc.net/problem/2610

풀이

먼저 bfs를 돌면서 연결된 회원들을 벡터 grp에 담는다.
(서로 아는 사이인 회원은 무조건 같은 위원회고, 위원회의 개수가 최대여야 하므로 그냥 아는 사이인 회원들끼리 같은 위원회에 넣어주면 된다. 아는 사람이 아무도 없으면 혼자서 위원회를 구성한다.)
위원회가 결정되었으면 위원회 회원들이 담긴 벡터 grp를 플로이드-와샬로..
플로이드-와샬을 통해 위원회의 각각의 회원으로부터 모든 회원까지의 거리를 구한다.
이 때 한 명의 회원으로부터 다른 회원들까지의 거리의 최댓값이 제일 작은 경우를 구한다.
그 회원이 해당 위원회의 위원장이 된다.
만약 위원회의 인원이 한명이라면 본인이 위원장이 되면 된다.
위원장 정보를 벡터 ans에 넣고,
마지막에 sort를 통해 정렬한 후 출력해주면 된다.

C++ 코드

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

using namespace std;

int N, M;
bool arr[101][101];
bool visit[101];
vector<int> ans;

void floydWarshall(vector<int> grp){
    int size = grp.size();
    if(size == 1){ans.push_back(grp[0]); return;}
    int d[101][101];
    
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            if (i == j) d[i][j] = 0;
            else if(arr[grp[i]][grp[j]] == true) d[i][j] = 1;
            else d[i][j] = size+1;
        }
    }
    
    for(int k=0; k<size; k++){
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                if(d[i][k] + d[k][j] < d[i][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    
    // 위원장
    int rep;
    int tmp = size+1;
    
    for(int i=0; i<size; i++){
        // 정점으로부터 다른 정점까지의 거리의 최대값이 제일 작은 정점 -> 위원장
        int dis = 0;
        for(int j=0; j<size; j++){
            dis = max(dis, d[i][j]);
        }
        if(dis < tmp){
            tmp = dis;
            rep = grp[i];
        }
    }
    
    ans.push_back(rep);
}

void bfs(int V){
    // 위원회 회원들을 담을 벡터 grp
    vector<int> grp;
    queue<int> q;
    q.push(V);
    visit[V] = true;
    
    while(!q.empty()) {
        V = q.front();
        grp.push_back(V);
        q.pop();
        for(int i=1; i<=N; i++) {
            if(visit[i] == true || arr[i][V] == false) continue;
            q.push(i);
            visit[i] = true;
        }
    }
    floydWarshall(grp);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N>>M;
    
    for(int i=0; i<M; i++){
        int a, b;
        cin>>a>>b;
        arr[a][b] = arr[b][a] = true;
    }
    
    for(int i=1; i<=N; i++){
        // 위원회 구성
        if(!visit[i])
            bfs(i);
    }
    
    cout<<ans.size()<<endl;
    
    sort(ans.begin(), ans.end());
    
    for(int i=0; i<ans.size(); i++){
        cout<<ans[i]<<endl;
    }
    
    return 0;
}