문제

[백준] 회의준비 (Gold 2)

요약

다음과 같은 규칙에 따라 위원회를 구성한다.

  1. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다.
  2. 위원회 수는 최대가 되어야 한다.

각 위원회의 위원들은 위원회의 대표를 통해서만 자신의 의사를 전달할 수 있다. 또, 각 위원들은 자신이 아는 사람을 통해서만 자신의 의견을 전달할 수 있다. 어떤 위원이 대표에게 의사를 전달하는 데 거쳐야 할 사람의 수를 의사전달시간이라 하자.

위원회의 모든 참석자들의 의사전달시간의 최댓값이 최소가 되도록 대표를 정하라. 구성되는 위원회의 수 K와 각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다. 한 위원회의 대표가 될 수 있는 사람이 둘 이상일 경우 그중 한 명만 출력하면 된다.

분류

  • 분리 집합
  • 플로이드-워셜

풀이

1. 내 풀이 (분리 집합, 플로이드-워셜)

  • 분리 집합을 이용해 총 몇 개의 위원회를 구성해야 하는지 알 수 있다.


import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = sys.maxsize

parent = [i for i in range(n)]
matrix = [[INF] * n for _ in range(n)]
for i in range(n):
    matrix[i][i] = 0


def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]


def union(s1, s2):
    if s1 < s2:
        parent[s2] = s1
    else:
        parent[s1] = s2


for _ in range(m):
    a, b = map(int, input().split())
    # 플로이드-워셜 세팅 : 서로 아는 관계를 1로.
    matrix[a - 1][b - 1] = 1
    matrix[b - 1][a - 1] = 1

    s1 = find(a - 1)
    s2 = find(b - 1)

    if s1 != s2:
        union(s1, s2)

for i in range(n):
    parent[i] = find(i)

# 플로이드-워셜 알고리즘으로 각 사람들 간의 거리 측정. => O(N^3) (N <= 100)
for k in range(n):
    for r in range(n):
        for c in range(n):
            matrix[r][c] = min(matrix[r][c], matrix[r][k] + matrix[k][c])

d = {}

for i, val in enumerate(parent):
    try:
        d[val].append(i)
    except:
        d[val] = [i]


print(len(set(parent)))
a = []
for key, arr in d.items():
    if len(arr) == 1: # 위원회에 위원이 1명 => 위원장
        a.append(key + 1)
    else:
        t = INF
        ans = 0
        for i in range(len(arr)): # i가 위원장이 된다면
            acc = 0
            for j in range(len(arr)): # j까지의 의사 전달 거리는?
                if i == j:
                    continue
                acc = max(acc, matrix[arr[i]][arr[j]]) # 최대 의사 전달 거리 갱신
            if acc < t: # 최대 의사 전달 거리의 최솟값 기록
                t = acc
                ans = arr[i] + 1
        a.append(ans) # 결정된 위원장 기록
a.sort()
for v in a:
    print(v) # 답변 출력