2660 - 회장뽑기

트리가 하나 주어지면 노드 하나를 잡고 이 노드를 회원이라고 합시다. 이 회원과 이어진 노드는 회원의 친구이고, 회원과 이어진 노드의 이어진 노드는 회원의 친구의 친구입니다. 회원이 모두와 친구라면 (해당 노드가 모든 노드와 직접적으로 이어져있다면) 점수 1, 회원의 친구의 친구가 존재한다면 점수2 ... 이런씩으로 갈 경우 점수가 제일 작은 회원을 회장이라 칭합니다. 이 회장이 될 수 있는 회원의 수와 회장의 점수, 그리고 회장 후보들을 오름차순으로 출력하는 문제입니다.

얼핏 보면 복잡해 보이지만 이 문제의 핵심은 BFS - LEVEL을 구하는 겁니다.
DFS와 같은 경우는 들어갈 때마다 depth + 1을 하고 재귀가 끝날 때 depth -= 1을 해서 깊이를 쉽게 구할 수 있습니다.
그러나 저희가 통상적으로 BFS의 깊이를 구할 경우는 많지 않기에 괜찮은 문제인 것 같습니다.

기본 선언

N = int(input())
que = deque()
graph = [[0]*(N+1) for _ in range(N+1)]
visited = [0]*(N+1)
depth = -1

BFS 사용을 위해 que와 그래프 방문여부 등을 받아줍니다.
자기자신은 깊이가 0이기 때문에 깊이 초기값은 -1부터 시작하겠습니다 (-1에 1 더하면 0이므로).

while True:
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1
    if a == -1 and b == -1:
        break

입력값이 각각 -1,-1이 나올 때까지 a와 b를 받고 그래프에 이어진 노드로 표현해줍시다.

ans = []
for i in range(1,N+1):
    ans.append(bfs(i))
    depth = -1
    visited = [0]*(N+1)

이제 각 노드(회원)마다 BFS를 돌린 후 한번 돌렸으면 다시 써먹을 수 있게 깊이와 방문여부를 초기화해줍니다.

BFS

from collections import deque

def bfs(chairman):
    global depth
    que.append(chairman)
    visited[chairman] = 1

deque를 import 하고 탐색을 시작하겠습니다.
일단 회장이라 변수를 chairman으로 두고 큐에 추가해준 다음 들어온 첫 노드를 방문처리 해주었습니다.

    while que:

이제 큐가 사라질 때 동안 돌리는건 항상 하던 일인데

        for _ in range(len(que)):

이게 이 문제의 핵심입니다. 들어온 que의 길이만큼만 일단 반복해서 해당 level을 유추해내도록 합시다.

예를 들어 루트노드5, 하위노드 1,2,3이 있다면 5일때 len(que)는 1이 나오고 한번만 돈 후 depth, 깊이를 +1 해주는 겁니다. 그리고 다시 1,2,3일때 len(que)는 3이 나오고 세번만 돈 후 depth, 깊이를 +1 해주는 씩으로 하면 BFS 탐색 중에서도 깊이를 구할 수 있습니다.

            chairman = que.popleft()
            for i in range(N+1):
                if visited[i] == 0 and graph[chairman][i] == 1:
                    visited[i] = 1
                    que.append(i) 

해당 노드와 연결된 노드를 탐색해서 방문처리해주고 que에 추가하여 다음 탐색지점으로 삼습니다.

        depth += 1
    return depth

그리고 들어온 que의 길이만큼의 반복이 끝나면 depth + 1을 해주고 while문으로 다시 들어가 탐색 후보 노드들을 탐색해줍니다. 최종적으로 depth를 return 해주면 이 회원의 친구 점수가 나옵니다.

출력

이 회장이 될 수 있는 회원의 수와 회장의 점수, 그리고 회장 후보들을 오름차순으로 출력해야 합니다.
아까 ans라는 배열에 회원마다 친구점수를 다 담아놨으므로

print(min(ans),ans.count(min(ans)))

가장 작은 점수와 가장 작은 점수를 가진 회원의 수(후보의 수)

for i in range(N):
    if ans[i] == min(ans):
        print(i+1,end=' ')

그리고 가장 작은 점수를 가진 회원들 (for문은 0부터 시작하므로 i+1하면 해당 회장후보 수로 치환가능)을 출력하면 문제 해결 가능합니다.