문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
#안해주면 런타임 에러 (recursive error)
sys.setrecursionlimit(10**6)
n = int(input())
tree = [[] for i in range(n+1)]
roots = [-1]*(n+1)
visited = [False]* (n+1)
for i in range(1,n):
a,b = map(int,input().split())
tree[a].append(b)
tree[b].append(a)
def dfs(x):
visited[x]=True
if not tree[x]:
return
for i in tree[x]:
if not visited[i]:
visited[i]=True
dfs(i)
roots[i] = x
return
dfs(1)
for i in roots[2:]:
print(i)
틀렸던 포인트
- setrecursionlimit을 안해줬었음 (N (2 ≤ N ≤ 100,000)) 파이썬의 재귀 깊이는 1000번 정도라서 보통 해줘야 한다고 한다.
- dfs 함수내에서 for문을 돌고 return을 안 써줬었고, 그 후에는 썼는데 for문 끝나고가 아니라 if문안에 썼었다 (이러면 for문 한번 돌고 끝나버린다.) 꼼꼼하게 봐야 한다.
- 무엇이 부모 노드인지 모르는 상태에서 두 정점 (노드)가 주어지기 때문에 tree[a].append(b)를 하고 tree[b].append(a)도 해주어야 했었는데 안해줌
다르게 짤 수 있던 포인트
- 다른 사람 코드를 보니 나처럼 비어있는 배열을 찾았을때 return되면서 호출 당한 노드를 호출한 노드의 부모로 넣어준게 아니라, 애초에 dfs 함수를 호출하기전에, x 노드를 i 노드의 부모 노드로 만들고, 재귀 함수를 호출했다. 어차피 끝까지 탐색을 해야 하기 때문에 이건 어떤 식으로 방문처리를 할거냐의 문제인 것 같다
- 비록 재귀지만 안에서 끝나는 조건을 설정해줄 필요 없었던게, for i in tree[x] 구문에서 만약 배열 내에 아무것도 없으면 그냥 return된다.