[백준 알고리즘] 2660.회장뽑기

 

 

 

오랜만에 BFS를 인접리스트를 활용해서 푸려니... 기억이 가물가물했다.ㅠ

 

 

회장후보를 구하려면 각사람마다 점수를 구하고, 각 사람의 점수들 중 가장 낮은 점수를 가진 사람들을 구해야 한다. 

 

그래서 간선의 시작점(사람)을 바꿔가면 각 시작점(사람)의 점수를 계산했고, 점수가 같을 경우에는 후보군에 추가시켰다.

 

visited 배열을 사용해서 방문체크와 점수 계산을 같이 했다.

 

 

from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)]
min_score = 51
candidate = []
while True:
    person1, person2 = map(int, input().split())
    if person1 == -1:
        break
    graph[person1].append(person2)
    graph[person2].append(person1)


def BFS(s, graph):
    global min_score, candidate
    visited = [0] * (N+1)
    Q = deque()
    Q.append(s)
    visited[s] = 1
    while Q:
        v = Q.popleft()
        for node in graph[v]:
            if visited[node] == 0:
                visited[node] = visited[v] + 1
                Q.append(node)
        if len(Q) == 0:
            score = visited[v] - 1

            if min_score > score:
                min_score = score
                candidate = [s]
            elif min_score == score:
                candidate.append(s)


# 각 사람마다 점수 체크하기
for start in range(1, N+1):
    BFS(start, graph)

print(min_score, len(candidate))
print(*candidate)