문제 설명
KOI 준비를 위해 회의를 개최하려 한다. 주최측에서는 회의에 참석하는 사람의 수와 참석자들 사이의 관계를 따져 하나 이상의 위원회를 구성하려고 한다. 위원회를 구성하는 방식은 다음과 같다.
- 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다.
- 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다.
이런 방식으로 위원회를 구성한 후에 각 위원회의 대표를 한 명씩 뽑아야 한다. 각 위원회의 대표만이 회의 시간 중 발언권을 가지며, 따라서 회의 참석자들이 자신의 의견을 말하기 위해서는 자신이 속한 위원회의 대표에게 자신의 의견을 전달해야 한다. 그런데 각 참석자는 자신이 알고 있는 사람에게만 의견을 전달할 수 있어 대표에게 의견을 전달하기 위해서는 때로 여러 사람을 거쳐야 한다. 대표에게 의견을 전달하는 경로가 여러 개 있을 경우에는 가장 적은 사람을 거치는 경로로 의견을 전달하며 이때 거치는 사람의 수를 참석자의 의사전달시간이라고 한다.
위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하시오.
예를 들어 1번, 2번, 3번 세 사람으로 구성되어 있는 위원회에서 1번과 2번, 2번과 3번이 서로 알고 있다고 하자. 1번이 대표가 되면 3번이 대표인 1번에게 의견을 전달하기 위해서 2번을 거쳐야만 한다. 반대로 3번이 대표가 되어도 1번이 대표인 3번에게 의견을 전달하려면 2번을 거쳐야만 한다. 하지만 2번이 대표가 되면 1번과 3번 둘 다 아무도 거치지 않고 대표에게 직접 의견을 전달 할 수 있다. 따라서 이와 같은 경우 2번이 대표가 되어야 한다.
https://www.acmicpc.net/problem/2610
제한 사항
풀이
문제를 요약하면 연결 관계가 있는 사람끼리는 같은 그룹으로 묶으면서 사람간의 거리의 최댓값이 가장 작은 대표를 선출하면 된다.
해당 문제를 작은 문제로 분할 하면 다음과 같다.
- 사람끼리의 거리를 구한다
- 관계가 있는 사람끼리는 하나의 그룹으로 만든다
우선 사람끼리의 거리를 구하는 이유는 같은 그룹의 속한 사람 간의 거리의 최댓값이 가장 적은 사람이 대표가 되어야 한다.
따라서 같은 그룹에 속하는 사람과의 모든 거리를 알아야 한다.
그룹을 나누고 각각 거리를 구하기 보다는 모든 사람끼리의 거리를 구하는 것이 더욱 간단하다.
따라서 플로이드-와샬 알고리즘을 이용하여 모든 사람끼리의 거리를 구하는 것이 좋다.
void CheckDistance()
{
for (int k = 1; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (i == j) continue;
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}모든 사람간의 거리를 구했다면 한 사람씩 순회하며 다른 사람과의 최대 거리를 기록해 놓는다.
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (dist[i][j] == MAX) continue;
maxDist[i] = max(maxDist[i], dist[i][j]);
}
}
이제 그룹으로 사람을 분리시키는 작업을 해보자.
그룹을 분리하는 과정은 DFS나 BFS로 그룹을 나눌 수 있지만 그 그룹에서 대표를 뽑는 과정이 있기 때문에 다른 방법을 사용하는 것이 좋다.
대표는 같은 그룹의 사람들과의 최대 거리가 최소인 사람이 되기 때문에 위에서 구해 놓은 최대 거리를 기준으로 유니온-파인드를 진행하면 된다.
int Find(int a)
{
if (parent[a] == a) return a;
return parent[a] = Find(parent[a]);
}
void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if (maxDist[a] > maxDist[b]) swap(a, b);
parent[b] = a;
}
이제 모든 조건들은 구했으니 이를 활용하여 정답을 만들면 된다.
모든 사람의 루트를 Find를 통해 구해놓고 set에 저장하면 정렬과 유일성이 보장된 결과를 만들 수 있다.
set<int> ans;
for (int i = 1; i <= N; i++)
{
ans.insert(Find(i));
}
cout << ans.size() << "\n";
for (auto a : ans)
{
cout << a << "\n";
}
전체 코드
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
using namespace std;
int N, M;
vector<vector<int>> dist;
vector<pair<int,int>> adj;
vector<int> maxDist;
vector<int> parent;
const int MAX = 987654321;
void CheckDistance()
{
for (int k = 1; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (i == j) continue;
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
int Find(int a)
{
if (parent[a] == a) return a;
return parent[a] = Find(parent[a]);
}
void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if (maxDist[a] > maxDist[b]) swap(a, b);
parent[b] = a;
}
int main()
{
INPUT_OPTIMIZE;
cin >> N >> M;
maxDist.resize(N + 1, 0);
parent.resize(N + 1);
dist.resize(N + 1, vector<int>(N + 1, MAX));
for (int i = 1; i <= N; i++)
{
parent[i] = i;
dist[i][i] = 0;
}
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
adj.push_back({ a,b });
dist[a][b] = 1;
dist[b][a] = 1;
}
CheckDistance();
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (dist[i][j] == MAX) continue;
maxDist[i] = max(maxDist[i], dist[i][j]);
}
}
for (auto& [a, b] : adj)
{
Union(a, b);
}
set<int> ans;
for (int i = 1; i <= N; i++)
{
ans.insert(Find(i));
}
cout << ans.size() << "\n";
for (auto a : ans)
{
cout << a << "\n";
}
return 0;
}