백준 11725번 : 트리의 부모 찾기 in Python

11725번: 트리의 부모 찾기

 

www.acmicpc.net

이 문제는 루트 없는 트리가 주어졌을 때 만약 트리의 루트를 1로 정하면 각 노드의 부모가 어떻게 되는지 구하는 문제이다.

이는 노드 1을 시작 노드으로 하는 그래프 탐색을 통해 구할 수 있다. 예전에 했던 DFS, BFS와 같은 그래프 탐색을 하면서 노드 k과 인접한 노드들을 방문할 때 인접한 노드들의 부모 노드를 노드 k으로 하는 방식으로 트리를 만들어 나간다. 그러면 그래프 탐색을 끝냈을 때 방문한 간선들과 노드들로 이루어진 트리를 만들 수 있다. 이때 이 트리는 노드 1을 루트 노드로 하고, 이후 각 간선에 이어진 노드들에 대해 먼저 방문한 노드는 나중한 방문한 노드의 부모 노드가 된다.

여기서는 BFS를 통해 그래프 탐색을 해서 각 노드의 부모 노드를 구했다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N = int(input())
# 각 노드의 부모 노드를 저장함으로써 트리를 나타내는 배열
tree = [-1 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
queue = deque()
queue.append(1)
# 루트 노드의 부모 노드는 없으므로 0으로 한다.
tree[1] = 0
while len(queue) > 0:
    u = queue.popleft()
    for v in graph[u]:
        if tree[v] == -1:
            # 노드 u와 인접한 노드들의 부모 노드로 u를 저장한다.
            tree[v] = u
            queue.append(v)
for i in range(2, N+1):
    print(tree[i])