[백준] 2660 - 회장 뽑기 [Python(파이썬)]

문제

https://www.acmicpc.net/problem/2660

2660번: 회장뽑기

 

풀이

그래프 탐색 문제였다. 각 노드를 기준으로 모든 노드에 대해 거리를 구해주는 문제였다. 모든 노드에 대해 거리를 구한다는 점에서 플로이드-와샬 알고리즘을 적용해서 푸는 방법도 있지만, 나는 BFS를 이용해서 풀었다.

 

언뜻 보면 복잡해보이지만, 아주 간단하다. 매 탐색시마다 visited를 초기화시키고, 인접한 노드를 방문할 때마다 거리를 기록해주면 된다. 별개의 리스트를 이용할 수도 있지만, 아래의 코드에선 메모리를 고려하여 거리를 visited에 기록했다.

 

그 후 visited 리스트를 순회하며 가장 먼 거리(=점수, max_dist)를 기록하고, 이것을 또 다시 딕셔너리에 노드(key): 점수(max_dist)의 형태로 저장해주면 된다. 마지막으로 최소 점수(min_dist)의 비교를 통해 결과를 도출한다. 

 

코드

import sys
from collections import deque, defaultdict

def bfs(start):
    queue = deque([[start, 0]])
    while queue:
        u, dist = queue.popleft()
        for v in g[u]:
            if not visited[v]:
                queue.append([v, dist+1])
                visited[v] = dist+1

def get_max_dist():
    max_dist = float('-inf')
    for dist in visited:
        if dist > max_dist:
            max_dist = dist
    return max_dist

n = int(sys.stdin.readline().strip())
g = defaultdict(list)
while True:
    a, b = map(int, sys.stdin.readline().split())
    g[a].append(b)
    g[b].append(a)
    if a == -1 and b == -1:
        break

result = defaultdict(int) # result = {회장후보: 점수}
for i in range(1, n+1):
    visited = [0 for _ in range(n+1)]
    visited[i] = 1
    bfs(i)
    result[i] = get_max_dist()

min_dist = min(result.values())
candis = [i for i, dist in result.items() if dist == min_dist]

print(min_dist, len(candis))
print(*candis) # 이미 입력순으로 정렬되어 있음