루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
일단 각 정점의 부모 번호를 저장할 parent
배열을 만듭니다. 이 때 루트의 부모는 자연스럽게 0
이 됩니다.
이후 BFS를 돌리면서 현재 노드와 연결되어 있는 노드를 조사합니다.
이때 next
가 cur
의 부모인지 확인해 만약 부모일 경우엔 건너뜁니다.
부모가 아니면 큐에 넣고 parend[next] = cur
로 만들어줍니다.
visited
를 사용할 때와 코드의 흐름이 크게 달라지지는 않습니다.
당연히 시간복잡도도 O(V+E)
로 동일한데, 트리에서는 E = V-1
이기에 그냥 O(V)
가 됩니다.
이렇게 parent
배열을 사용해서 root 번호의 정점을 루트로 두었을 때 각 정점의 부모 정보를 BFS 한 번으로 알아낼 수 있습니다. 부모 정보가 필요한 문제에서는 이를 활용할 수 있습니다.
import sys
from collections import deque
def bfs(graph):
q = deque([1])
parent = [0] * 100001 # parent[i] = j -> i의 부모노드가 j
while q:
cur = q.popleft()
for next in graph[cur]:
# 현재 노드의 부모가 다음 노드라면
# 즉, 다음 노드가 자식이 아니라 부모노드라면
if parent[cur] == next:
continue
parent[next] = cur
q.append(next)
return parent
if __name__ == "__main__":
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
parent = bfs(graph)
for i in range(2, n + 1):
print(parent[i])