[백준] 2610번 회의준비 (파이썬)

문제링크 https://www.acmicpc.net/problem/2610

난이도 : GOLD II

문제해결 아이디어

• 유니온 파인드를 통해 하나의 부모 노드를 가리키도록 한 뒤
• 같은 부모를 가리키는 인덱스끼리 dictionary로 정리하고
• 각각의 value 값중에 최소 거리를 가지는 값을 BFS로 탐색한뒤 answer에 추가한다.

소스코드

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
from collections import deque

n = int(input())
m = int(input())

parent = [i for i in range(n+1)]
graph = [[] for _ in range(n+1)]

def union(x,y):
    x = find(x)
    y = find(y)
    parent[max(x,y)] = min(x,y)

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

for _ in range(m):
    a,b = map(int, input().split())
    union(a,b)
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1): find(i)

groups = {i:[] for i in set(parent) if i != 0}

for i in range(1, n+1):
    groups[parent[i]].append(i)

def BFS(g):
    dist = 0
    q = deque([g])
    v = set(q)
    while q:
        for _ in range(len(q)): # depth check
            x = q.popleft()
            for node in graph[x]:
                if node in v:
                    continue
                v.add(node)
                q.append(node)
        dist += 1
    return dist

answer = []

for group in groups.values():
    time = int(1e9)
    for g in group:
        t = BFS(g)
        if t < time:
            time = t
            president = g
    answer.append(president)

print(*[len(answer)] +sorted(answer))