[백준] 11725번 : 트리의 부모 찾기 (Python)

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

 

 

import sys

sys.setrecursionlimit(10**6) # 재귀 제한 설정
input = sys.stdin.readline

N = int(input()) # 노드 수

visited = [False]*(N+1) # 방문 기록 저장
tree = [[] for _ in range(N+1)] # 인접 리스트
answer = [0]*(N+1) # 정답 리스트
  
# 트리 저장
for i in range(1, N):
    s, e = map(int, input().split())

    # 양방향 저장
    tree[s].append(e)
    tree[e].append(s)

# DFS 구현
def DFS(n):
    
    visited[n]=True # 방문

    for i in tree[n]:
        if not (visited[i]): # 미방문 노드일 경우에만
            answer[i] = n # 정답 노드에 부모 노드 저장
            DFS(i) # 자식 노드로 이동
    
DFS(1) # DFS 실행

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

 

 

[문제풀이]

---

 

이 문제는 DFS를 구현할 수 있고, DFS를 통해 트리를 탐색할 수 있어야 한다.

DFS로 가기 직전의 노드가 부모 노드란걸 알고 있으면 쉽게 풀 수 있는 문제다.

인접 리스트로 그래프, 혹은 트리를 저장할 때 가장 일반적으로 쓰는 탐색이 DFS, BFS다.

트리의 루트가 1이라고 지정되어 있기 때문에 1번 노드부터 DFS로 탐색하면서 부모 노드를 찾아 주면 된다.

 

DFS 탐색 → 다음 미방문 노드의 부모노드는 현재노드 → 저장

 

BFS가 아닌 DFS를 사용하는 이유는 요렇다.

자식 노드로 가기 직전의 현재 노드가 다음번에 탐색할 노드의 부모 노드이기 때문!

 

이때 재귀 함수를 사용하는 경우의 DFS는 sys.setrecursionlimit()을 설정해 재귀 제한 횟수를 늘려줘야 한다.

파이썬에서 기본 재귀 제한이 천 번인데, 그게 너무 낮아서 로직이 다 맞아도 걸려서 안 풀리는 경우가 있기 때문!