[Python] 백준 11725번: DFS로 트리 순회

📎 백준 11725번 풀러 가기!

11725번: 트리의 부모 찾기

문제

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

입력

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

출력

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

---

오늘은 트리 문제이다!

 

트리의 부모를 구하는 프로그램인데,

DFS가 깊이 우선 순회라는 점을 이용해

DFS를 통하여 순회하면 쉽게 각 노드의 부모를 찾아줄 수 있다.

 

다만, 여기서 주의해야할 점은 파이썬은 default로 재귀호출을 1000번까지 허용하기 때문에재귀호출의 수를 늘려줘야 런타임 에러가 발생하지 않는다는 점이다.

 

파이썬에서 재귀호출의 수는

 

import sys

sys.setrecursionlimit(늘릴 수)

 

로 늘려줄 수 있다.

 

이렇게 오늘도 문제 하나 완료!

---

아래는 내가 구현한 코드👇

import sys
sys.setrecursionlimit(10**9)

N = int(sys.stdin.readline())

visited = [False] * (N + 1)
tree = {x:[] for x in range(N + 1)}
ans = {x:[] for x in range(N + 1)}

for _ in range(N - 1):
    v1, v2 = map(int , sys.stdin.readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)

def dfs(node):
    visited[node] = True
    for x in tree[node]:
        if not visited[x]:
            dfs(x)
            ans[x] = node

dfs(1)

for x in range(2, N + 1):
    print(ans[x])