[백준] 11725번 트리의 부모 찾기 해설 및 풀이 (Python)

백준 11725번 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

 

---

문제

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

입력

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

출력

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

---

문제 유형

 

그래프 이론

그래프 탐색

트리

너비 우선 탐색

깊이 우선 탐색

 

풀이 방법 도출

1. 트리는 n+1 크기의 리스트를 만들어 인접 리스트 형식으로 저장합니다.
2. 주어진 간선 정보를 통해 양방향으로 연결합니다.
3. 루트 노드를 1로 설정하고 DFS 탐색을 수행합니다.
4. DFS를 이용하여 방문한 노드의 부모를 기록합니다.
5. 방문하지 않은 노드만 탐색하며, 이미 방문한 노드는 건너뜁니다.
6. 2번 노드부터 N번 노드까지 부모 노드를 출력합니다.

 

시간 복잡도

• 트리 생성 : O(N)
• DFS 탐색 : O(N)
• 출력 : O(N)
• 총 시간 복잡도 : O(N)

---

핵심 코드 삽입 및 설명

import sys

sys.setrecursionlimit(10**6)  # 재귀 깊이 제한 증가
input = sys.stdin.readline  # 빠른 입력 사용

n = int(input())  # 노드 개수 입력

# 트리 생성 
tree = [[] for _ in range(n+1)]

# 간선 정보 입력
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# 부모 노드를 저장할 리스트
parents = [0] * (n+1)  # 부모 정보 저장 

def dfs(node, parent):
    parents[node] = parent  # 현재 노드의 부모 기록
    for child in tree[node]:  # 현재 노드와 연결된 자식 노드 탐색
        if child != parent:  # 방문하지 않은 노드만 탐색
            dfs(child, node)

# DFS 수행
dfs(1, 0)

# 2번 노드부터 N번 노드까지 부모 노드 출력
for i in range(2, n+1):
    print(parents[i])