회의준비
문제 해석
위원회에서 모든 참석자들의 의사전달시간 중, 최댓값이 최소가 되도록 대표를 정하는 문제입니다.
참석자는 대표에게 의견을 전달하는데 여러 사람을 거쳐갈 수 있습니다. 대표에게 전달되기까지의 최단 경로의 수를 의사전달시간이라고 합니다.
각 위원회의 대표 번호를 작은수부터 차례대로 한 줄에 하나씩 출력합니다.
한 위원회의 대표가 될 수 있는 사람이 둘 이상일 경우 그중 한명만 출력하면 됩니다.
설계(10)
모든 노드 간의 최단 경로를 구하고, 각 그룹 별로 의사전달 시간이 최소인 노드를 찾아야 합니다.
따라서, O(N^3)의 시간복잡도인 플로이드 와샬 알고리즘을 사용하면 될 것으로 보입니다.
첫번째로, 플로이드 와샬 알고리즘으로 모든 최단 경로를 구합니다.
두번째로, boolean 배열과 벡터를 이용하여 각 그룹을 구분합니다.
이후, 각 그룹별로 의사전달시간의 최댓값의 최소를 구합니다.
마지막으로 정해진 대표의 노드를 오름차순으로 정렬한 후 출력하면 됩니다.
구현(20)
코드(c++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 101
#define INF 987654321
int N, M;
int arr[MAXN][MAXN];
vector<vector<int> > adj;
bool flag[MAXN];
vector<int> ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) continue;
arr[i][j] = INF;
}
}
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
arr[u][v] = 1;
arr[v][u] = 1;
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
for (int i = 1; i <= N; i++) {
if (flag[i]) continue;
flag[i] = true;
vector<int> tmp;
tmp.push_back(i);
for (int j = 1; j <= N; j++) {
if (i == j || arr[i][j]==INF) continue;
tmp.push_back(j);
flag[j] = true;
}
adj.push_back(tmp);
}
for (int i = 0; i < adj.size(); i++) {
int min_v = INF;
int num = 0;
for (int j = 0; j < adj[i].size(); j++) {
int max_tmp = 0;
for (int k = 1; k <= N; k++) {
if (arr[adj[i][j]][k] == INF) continue;
max_tmp = max(max_tmp,arr[adj[i][j]][k]);
}
if (max_tmp < min_v) {
num = adj[i][j];
min_v = max_tmp;
}
}
ans.push_back(num);
}
sort(ans.begin(), ans.end());
cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << "\n";
}
return 0;
}
코드(python)
N = int(input())
M = int(input())
INF = 987654321
arr = [[INF if i!=j else 0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
u,v = map(int,input().split())
arr[u][v] = arr[v][u] = 1
adj = list()
flag = [False for _ in range(N+1)]
for k in range(1,N+1):
for i in range(1,N+1):
for j in range(1,N+1):
arr[i][j] = min(arr[i][j],arr[i][k]+arr[k][j]);
for i in range(1,N+1):
if flag[i]==True:
continue
flag[i] = True
tmp = list()
tmp.append(i)
for j in range(1,N+1):
if i == j or arr[i][j] == INF:
continue
flag[j] = True
tmp.append(j)
adj.append(tmp)
ans= list()
for v in adj:
min_v = INF
num = 0
for idx in v:
tmp = 0
for j in range(1,N+1):
if arr[idx][j]==INF:
continue
tmp = max(tmp,arr[idx][j])
if min_v > tmp:
min_v = tmp
num = idx
ans.append(num)
ans.sort()
print(len(ans))
for i in ans:
print(i)
디버깅
출력 부분에서 대표 번호를 오름차순으로 정렬하라는 지문을 읽지 않아서 정렬하지 않는 실수를 하였습니다.
제출결과
0 ms (c++) 228 ms (pypy3)
마무리
플로이드 와샬 알고리즘을 사용하는 문제였습니다. 모든 최단 경로를 구해야한다는 아이디어를 생각할 수 있으면 무난하게 풀 수 있을 것입니다.