[백준] 11725 트리의 부모 찾기

문제

• 루트 없는 트리가 주어진다.
• 트리의 루트가 1이라고 정했을 때, 각 노드의 부모를 구하기
• 2 <= N <= 100,000

 

풀이

• 각 노드의 연결정보를 입력한 다음, 1번 노드부터 시작해서 연결된 노드들을 추가한다.
• 이때, 1번과 연결된 노드는 모두 부모를 1번으로 두고 있는 부모라고 할 수 있다.
• 트리이므로 부모 노드가 1개이기 때문에 BFS 또는 DFS로 확인이 가능하다.

 

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
# 각 간선 저장하기
trees = [[] for _ in range(N+1)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    trees[a].append(b)
    trees[b].append(a)


q = deque([1])	# 1번 노드(루트)부터 시작해서
parents = [0 for i in range(N+1)]	# 부모 노드 저장
while q :
    now = q.popleft()
    # 현재 노드와 연결된 노드들을 확인
    for i in trees[now] :			
        if parents[i] == 0 and i != 1 :
            parents[i] = now
            q.append(i)

# 출력
for i in range(2, N+1) :
    print(parents[i])

 

References

• 백준 그래프 탐색