[탐색/DFS] 백준 11725 트리의 부모 찾기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11725번: 트리의 부모 찾기

 

 

 

2. 문제 풀이

 주어진 트리의 루트를 1이라고 했을 때, 각 노드의 부모를 구해야 합니다.

 

루트 없는 트리 / 루트가 1인 트리

 예제 입력 1번을 살펴보겠습니다. 트리의 루트를 1번으로 했을 때, 정렬하면 오른쪽과 같습니다. 사실 보기 좋게 만들기 위해서 오른쪽으로 정렬해둔 것이지, 컴퓨터 입장에서는 둘 다 같습니다.

 

 

2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

 트리 구조로 입력을 받은 뒤에는, 1번부터 탐색을 시작합니다. DFS/BFS 모두 가능하지만 저는 DFS를 사용하겠습니다. 노드 끝까지 탐색하며, 부모노드가 확인되지 않은 노드를 발견하면 이전 노드를 부모 노드로 저장합니다.

 

 

 

3. 코드

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

# 입력
N = int(input())
tree = [[] for _ in range(N+1)]  # 트리
parents = [0]*(N+1)  # 부모노드 저장

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

 DFS 탐색은 재귀를 활용하므로, sys.setrecursionlimit를 10**9까지 넉넉히 높여줍니다.

 

 

# DFS 탐색
def dfs(start, tree, parents):
    # 부모가 없으면 부모 설정 후, DFS 탐색
    for i in tree[start]:
        if parents[i] == 0:
            parents[i] = start
            dfs(i, tree, parents)

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

 DFS 탐색으로 leaf노드까지 탐색하며, 부모 노드를 체크합니다. 1번 노드가 최상위 루트 노드이므로, 1번에서 DFS 탐색을 실행하면 모든 노드를 순회합니다.