회의에 참여하는 참석자들간의 관계가 간선정보로 주어지고 해당 관계를 가지는 사람들은 하나의 위원회로 구성되어야 한다.
그렇게 구성된 위원회의 구성원과 관계가 없는 참석자들은 다른 그룹을 생성하게 되고 이 그룹의 개수와 그룹내에서 연결된 참석자들과 가장 최단 거리로 연결되며, 각 참석자까지의 거리의 최대값이 가장 작은 참석자를 찾아야 하는 문제이다.
먼저 각 그룹정보를 추려내기 위해 유니온 파인드 알고리즘을 사용하여 각 참석자들이 같은 그룹에 속하는지를 알아 낼수 있도록 했다.
다음으로 플로이드 와샬 알고리즘을 이용하여 하나의 정점(참석자)가 도달할 수 있는 모든 정점의 최단 거리를 구했다.(이때 도달할 수 없는(다른 그룹) 참석자의 가중치는 0이 된다.)
다음 두 과정을 통해 각 그룹의 개수와 정보, 각 정점가 도달할 수 있는 최단 거리 정보를 알아 낼수 있다.
이제는 이 정보를 각 그룹을 기준으로 추려나가기만 하면 된다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
int dp[101]; // 그룹 정보를 담을 변수
int metrix[101][101];
struct S {
int node;
int cost;
};
S buf[101]{}; // 그룹번호와 위원장 정보를 담을 변수
int find(int n) {
if (dp[n] == 0)
return n;
return dp[n] = find(dp[n]);
}
bool cmp(S& a, S& b) {
return a.node < b.node;
}
int main() {
cin >> N >> M;
int a, b;
for (int i = 0; i < M; i++) {
cin >> a >> b;
//그룹 정보 수집
int A = find(a);
int B = find(b);
if (A != B) dp[A] = B;
metrix[a][b] = 1;
metrix[b][a] = 1;
}
//각 하나의 정점에서 모든 정점까지의 최단 거리를 계산
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= N; k++) {
for (int j = 1; j <= N; j++) {
if (metrix[k][i] && metrix[i][j]) {//1이상으로 경로가 존재할 경우
if (!metrix[k][j] || metrix[k][j] > metrix[k][i] + metrix[i][j]) { //경로가 갱신되지 않았거나 새로운 경로가 비용이 더 작을 경우
metrix[k][j] = metrix[k][i] + metrix[i][j];
}
}
}
}
}
// 계산된 최단거리를 기준으로 속해있는 그룹의 위원장시 최대값 비용을 기준으로 정점 정보를 갱신
for (int i = 1; i <= N; i++) {
int cost = 1;
for (int k = 1; k <= N; k++) {
if (i != k && cost < metrix[i][k]) cost = metrix[i][k];
}
int group = find(i);
if (buf[group].cost == 0 || buf[group].cost > cost) {
buf[group].cost = cost;
buf[group].node = i;
}
}
//그룹별 최소비용 정보를 벡터에 저장
vector<S> result;
for (int i = 1; i <= N; i++) {
if (buf[i].cost != 0) result.push_back(buf[i]);
}
//정점의 숫자를 기준으로 정렬
sort(result.begin(), result.end(), cmp);
cout << result.size() << "\n";
for (auto& res : result) {
cout << res.node << "\n";
}
}