[Python] BOJ 2660 - 회장뽑기

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

2660번: 회장뽑기

# BFS 문제이다.

 

# 1번 후보부터 N번 후보까지 각각 bfs함수를 실행해 dist값을 갱신해준다.

   (dist값 = 현재 후보와의 거리 = 문제에서 요구하는 '점수')

 

# dist값의 최대가 현재 후보의 점수이다. 따라서 점수가 가장 작은 사람이 회장후보이므로

   chairman 배열에 회장후보들을 넣어준다. 

   마지막에 점수와, 후보 수, 후보들을 출력해주면 끝

 

import sys
from collections import deque
input = sys.stdin.readline
q = deque()
N = int(input())
friend = [[] for _ in range(N+1)]
while True:
	a, b = map(int,input().split())
	if a == -1:
		break
	else:
		friend[a].append(b)
		friend[b].append(a)

# bfs함수
def bfs(n):
	visited[n] = True
	q.append(n)
	while q:
		x = q.popleft()
		for i in friend[x]:
			if not visited[i]:
				q.append(i)
				dist[i] = dist[x] + 1
				visited[i] = True

chairman = []
dab = 51
for i in range(1, N+1):
	dist = [0] * (N+1)
	visited = [False] * (N+1)
	bfs(i)
	m = max(dist)
	if m == dab:
		chairman.append(i)
	elif m < dab:
		chairman = [i]
		dab = m

print(dab, len(chairman))
print(*chairman)

(solved.ac 티어: 골드 5)