[백준 2660번] 회장 뽑기 -python

문제 링크

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

2660번: 회장뽑기

풀이 

- bfs 문제

- 각 노드를 기준으로 모든 노드에 대해 거리를 구하는 문제 

- 각 노드마다 visited 를 초기화하여 다른 노드까지 거리를 구한 후 최댓값을 딕셔너리 result에 기록 

- result의 value들의 최솟값 출력

- result의 최솟값을 value로 가진 key를 answer에 추가 

- answer의 개수 출력하고, answer 오름차순으로 정렬하여 출력 

import collections 

def bfs(v):
  # visited 배열 초기화 
  visited = [0] * (n+1)
  visited[v] = 1 
  
  q = collections.deque()
  q.append((v,0))

  while q :
    t, index = q.popleft()

    for u in maps[t]:
      if visited[u] == 0:
      # 거리 증가 
        visited[u] = index + 1 
        q.append((u,index+1))
  
  # 거리의 최댓값 리턴 
  return(max(visited))

n = int(input())

maps = collections.defaultdict(list)

while True:
  a, b = map(int,input().split()) 

  if a == -1 and b == -1 :
    break
  
  maps[a].append(b)
  maps[b].append(a)

result = collections.defaultdict(int)

for i in range(1,n+1):
  tmp = bfs(i)
  result[i] = tmp

min_num = min(result.values())

print(min_num, end = " ")

answer = []

for i, num in result.items():
  if num == min_num:
    answer.append(i)

answer.sort()

print(len(answer))
print(" ".join(map(str,answer)))