[정글 알고리즘] - [중] -백준 11725 트리의 부모 찾기 풀이- 실버2

문제 요약

항목	설명
입력	노드 수 N, 그리고 N-1개의 간선 정보
중요	간선은 부모→자식 방향이 아니라 그냥 연결 정보
루트	1번 노드를 루트로 고정
출력	2번 노드부터 N번 노드까지의 부모 노드 번호

문제에서 주어지는 간선은 “누가 부모인지”를 알려주는 것이 아니라 “두 노드가 연결되어 있다”는 정보입니다. 그래서 반드시 1번에서 시작해 탐색하며 부모를 정해야 합니다.

가장 많이 헷갈리는 부분

헷갈림 포인트

예제 입력에 1 6, 4 1 같은 줄이 섞여 있으니까 “그럼 1의 부모가 6인가?”, “왜 출력에서 부모가 1인 노드가 여러 개 나오지?” 하고 헷갈리기 쉽습니다.

정답 해석

1 6은 “1이 6의 부모다”가 아닙니다.

그냥 1번 노드와 6번 노드가 연결되어 있다는 뜻입니다.

부모 관계는 입력 순간에 정해지는 것이 아니라, 1을 루트로 잡고 DFS/BFS로 따라가면서 정해집니다.

예제 1 시각화

예제 입력의 간선

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

이건 방향이 없는 연결 정보입니다. 아직 부모/자식은 정해지지 않은 상태입니다.

1을 루트로 놓고 펼치면

1

／　　　＼

6 4

|

／　＼

3

|

5

2 7

노드	부모
2	4
3	6
4	1
5	3
6	1
7	4

왜 1이 두 번 나오나?

4의 부모도 1이고, 6의 부모도 1이기 때문입니다. 부모가 1인 노드가 여러 개 있는 것은 전혀 이상하지 않습니다. 한 부모가 여러 자식을 가질 수 있기 때문입니다.

핵심 아이디어

1. 입력은 부모 정보가 아니다

간선 입력 a b는 a와 b가 연결되어 있다는 뜻입니다. 따라서 바로 parent[a] = b처럼 저장하면 안 됩니다.

2. 먼저 그래프를 만든다

무방향 트리이므로 인접 리스트를 만들 때는 graph[a].append(b), graph[b].append(a) 둘 다 해줘야 합니다.

3. 1번부터 탐색하면서 부모를 기록한다

현재 노드가 node이고, 다음 노드가 next_node일 때, 아직 방문하지 않았다면 parent[next_node] = node로 기록하면 됩니다.

탐색 흐름 시각화

DFS로 부모를 채우는 느낌

시작 : 1 → 6 방문 → parent[6] = 1 → 3 방문 → parent[3] = 6 → 5 방문 → parent[5] = 3

핵심은 “입력으로 부모를 받는 것”이 아니라, 탐색하면서 처음 방문하게 만든 현재 노드를 부모로 기록하는 것입니다.

현재 노드	다음 노드	처리
1	6	parent[6] = 1
6	3	parent[3] = 6
3	5	parent[5] = 3
1	4	parent[4] = 1

최종 코드

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

n = int(input())
graph = [[] for _ in range(n + 1)]

parent = [0] * (n + 1)
visited = [False] * (n + 1)

for _ in range(n - 1):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

def dfs(node):
    visited[node] = True

    for next_node in graph[node]:
        if not visited[next_node]:
            parent[next_node] = node
            dfs(next_node)

dfs(1)

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

코드 한 줄씩 설명

줄	코드	설명
1	import sys	재귀 제한 설정과 빠른 입력을 위해 sys 모듈을 불러옵니다.
2	sys.setrecursionlimit(10**6)	노드 수가 최대 100,000개라서 트리가 한 줄처럼 길게 들어오면 재귀 깊이가 매우 깊어질 수 있습니다. 파이썬 기본 재귀 제한은 낮기 때문에, 이를 늘려서 RecursionError를 방지합니다. [Source](https://www.acmicpc.net/problem/11725)
3	input = sys.stdin.readline	입력 속도를 높이기 위해 기본 input() 대신 빠른 입력을 사용합니다. 노드 수가 큰 문제에서는 이런 최적화가 꽤 체감됩니다.
4		입력부와 본문을 나누기 위한 공백 줄입니다.
5	n = int(input())	노드의 개수 N을 입력받습니다.
6	graph = [[] for _ in range(n + 1)]	인접 리스트를 만듭니다. 노드 번호가 1번부터 시작하므로 n + 1 크기로 잡습니다. graph[x]에는 x와 연결된 노드들이 들어갑니다.
7		배열 선언 구간 구분용 공백입니다.
8	parent = [0] * (n + 1)	각 노드의 부모를 저장할 배열입니다. 나중에 parent[x]에는 x의 부모 번호가 들어갑니다.
9	visited = [False] * (n + 1)	방문 여부를 기록하는 배열입니다. 트리는 무방향 그래프처럼 저장되므로 방문 체크를 하지 않으면 부모에서 자식으로 갔다가 다시 부모로 돌아가는 식으로 무한 반복될 수 있습니다.
10		이제 간선 입력을 처리합니다.
11	for _ in range(n - 1):	트리의 간선 수는 항상 n - 1개이므로 그만큼 반복합니다. [Source](https://www.acmicpc.net/problem/11725)
12	node1, node2 = map(int, input().split())	연결된 두 노드를 입력받습니다. 여기서 중요한 점은 이 둘이 부모/자식 관계가 아니라는 것입니다.
13	graph[node1].append(node2)	node1과 node2가 연결되어 있으므로 node1의 인접 리스트에 node2를 넣습니다.
14	graph[node2].append(node1)	무방향 연결이므로 반대 방향도 함께 넣어야 합니다. 그래서 양쪽에 모두 append 합니다.
15		이제 DFS 함수를 정의합니다.
16	def dfs(node):	현재 노드를 기준으로 연결된 자식 방향을 따라 내려가며 부모를 기록하는 함수입니다.
17	visited[node] = True	현재 노드를 방문 처리합니다. 이 줄이 초반에 있어야 다시 부모 방향으로 되돌아가서 재귀가 꼬이지 않습니다.
18		현재 노드와 연결된 다음 노드들을 살펴봅니다.
19	for next_node in graph[node]:	현재 노드와 연결된 모든 이웃 노드를 순회합니다.
20	if not visited[next_node]:	아직 방문하지 않은 노드라면, 현재 노드에서 처음 도달한 것이므로 부모를 정할 수 있습니다.
21	parent[next_node] = node	이 문제의 핵심 한 줄입니다. 현재 노드 node를 통해 처음 next_node에 도달했으므로, next_node의 부모는 node입니다.
22	dfs(next_node)	방금 부모를 기록한 next_node를 기준으로 다시 깊이 탐색을 이어갑니다.
23		이제 루트 1에서 탐색을 시작합니다.
24	dfs(1)	루트를 1번 노드로 정했으므로 1에서 시작해 전체 트리를 탐색합니다.
25		마지막으로 2번부터 N번까지 부모를 출력합니다.
26	for i in range(2, n + 1):	문제에서 1번은 루트이므로 출력하지 않고, 2번 노드부터 부모를 출력합니다. [Source](https://www.acmicpc.net/problem/11725)
27	print(parent[i])	i번 노드의 부모를 한 줄에 하나씩 출력합니다.

왜 처음 시도는 틀렸을까?

잘못된 생각

parent[node1] = node2

이 방식은 입력 줄을 보는 순간 바로 부모를 확정해버립니다. 하지만 문제의 입력은 연결 정보일 뿐이므로, 어떤 쪽이 부모인지 아직 모르는 상태입니다.

반례 감각

예를 들어 입력에 4 1이 있다고 해서 바로 parent[4] = 1만 생각하는 건 위험합니다.

부모 관계는 반드시 1을 루트로 잡고 전체 연결을 따라가 본 뒤 결정해야 합니다.

실전 팁

1. 재귀 DFS는 런타임 에러가 날 수 있다

노드 수가 100,000개까지 가능하므로, 트리가 한쪽으로 길게 늘어지면 재귀 깊이도 매우 깊어집니다. 이때 sys.setrecursionlimit(10**6)이 없으면 재귀 깊이 초과가 날 수 있습니다. [Source](https://www.acmicpc.net/problem/11725)

2. 입력 속도 최적화가 체감된다

이 문제는 간선 입력이 많기 때문에 input = sys.stdin.readline을 사용하면 실행 시간이 꽤 줄어듭니다.

3. BFS로도 풀 수 있다

부모를 기록하는 핵심 로직은 같습니다. 탐색 방식만 DFS 대신 BFS로 바꿔도 정답이 됩니다.

마무리 정리

이 문제의 핵심 한 문장

입력의 간선은 부모 정보가 아니라 연결 정보이므로, 1번을 루트로 잡고 DFS/BFS를 하면서 처음 방문한 노드의 부모를 기록해야 합니다.

문제는 루트 없는 트리가 주어졌을 때, 1번을 루트로 정한 뒤 각 노드의 부모를 찾는 것입니다. 따라서 입력을 바로 부모 배열에 넣는 것이 아니라, 먼저 그래프로 저장한 뒤 탐색하면서 부모를 채워야 합니다.