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

Hyun·2025년 3월 25일

백준

목록 보기

90/92

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

4
6
1
3
1
4

예제 입력 2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2

1
1
2
3
3
4
4
5
5
6
6

풀이

트리 유형이 익숙하지 않아서 좀 오래 걸렸다.
루트 없는 트리가 주어지고, 트리의 루트가 1이라고 하길래, 노드 번호 순대로 트리가 형성되는 것으로 생각했는데, 그런게 아니더라.

노드 번호는 노드의 식별값일 뿐, 번호가 낮다고 해서 트리의 상단에 위치하는게 아니었다.

그리고 이 문제는 트리 문제이기 때문에 모든 노드가 연결되어 있어야 한다. 따라서 떨어져 있는 노드 집합은 존재하지 않는다.

각 노드의 부모를 구하기 위해 해당 트리를 dfs 로 탐색하며 직전 노드를 방문하지 않았으면서 새로 탐색할 노드의 부모로 기록한다.

루트로 지정된 1번 노드에서 출발하기 때문에 방문한 적이 없으면서 새로 탐색할 노드의 직전 노드가 무조건 부모노드이다. dfs 의 탐색 방식을 생각해보면 이해할 수 있다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input()) # n 개의 정점 연결 정보
graph = [ [] for _ in range(n+1)] # n+1 개의 배열

# 노드간 연결 정보 입력 받음
for _ in range(n-1):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

# 노드별 연결 정보 정렬 <- 정렬 안해도 이 문제 풀 수 있음
for sub_arr in graph:
    sub_arr.sort()

# DFS
visited = [0] * (n+1) # 방문 기록
p = [0] * (n+1) # 부모 노드 정보 기록, p[i]: 노드 i 의 부모 노드 번호
# 들어가기 전 방문 여부 확인, 들어가서 방문 처리
# 직전 노드가 부모 노드임
def dfs(graph, node, visited): 
    visited[node] = 1 # 현재 노드 방문 처리

    for v in graph[node]:
        if visited[v] == 0: # 방문 여부 확인
            p[v] = node # 부모 노드 기록
            dfs(graph, v, visited)

dfs(graph, 1, visited)

for i in range(2, n+1):
    print(p[i])