[백준][Python] 2660번 회장뽑기 - 코팩

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

2660번: 회장뽑기

풀이

모든 사람과 친구관계로 이어져 있어야하며 중간에 연결해주는 친구가 적을수록 회장이 될 수 있는 후보단에 들어갈 수 있습니다.

BSF알고리즘을 이용해주었습니다. 직접적인 친구가 아닌 간접적인 친구의 계산을 위해서 deque에 이어주는 친구의 수를 계산해주는 변수를 추가해주었습니다.

코드

# 2660번 회장뽑기
import sys
from collections import deque

input = sys.stdin.readline

INF = int(1e9)

n = int(input())
graph = [[] for i in range(n+1)]
while 1:
    a, b = map(int, input().split())
    if a == -1:
        break
    graph[a].append(b)
    graph[b].append(a)

def bfs(s):
    queue = deque([])
    queue.append([s, 0])
    visited = [False] * (n+1)
    visited[s] = True
    score = -1
    while queue:
        cur_p, cur_score = queue.popleft()
        for f in graph[cur_p]:
            if visited[f] == False:
                visited[f] = True
                score = max(score, cur_score+1)
                queue.append([f, cur_score+1])
    for i in range(1,n+1):
        if not visited[i]:
            return INF
    return score

cand = []
min_score = INF
for j in range(1, n+1):
    temp = bfs(j)
    if temp == INF:
        continue
    if temp < min_score:
        cand = []
        cand.append(j)
        min_score = temp
    elif temp == min_score:
        cand.append(j)

print(min_score, len(cand))
print(" ".join(list(map(str, sorted(cand)))))

출력결과