문제
https://www.acmicpc.net/problem/19641
접근
- 각 노드에 대해 방문하는 순서가 필요해서 dfs를 이용했다.
- dfs의 매개변수로 순서를 넘길 경우 같은 레벨에 있는 노드들을 처리하기가 힘들어서 공유변수 order를 이용해서 처리했다.
- 주의할 점은 노드를 오름차순으로 방문하므로, 연결정보를 입력받은 후 정렬해줘야 한다.
풀이
- 각 노드를 방문하면 order를 1 증가시키고 left 값을 기록한다.
- 해당 노드와 연결된 다른 노드들을 방문한다.
- 방문이 완료되면 order를 1 증가시키고 right 값을 기록한다.
import sys
sys.setrecursionlimit(10 ** 5)
def dfs(now):
global order
order += 1
left[now] = order
for nxt in tree[now]:
if left[nxt] == 0:
dfs(nxt)
order += 1
right[now] = order
n = int(input())
tree = [[] for _ in range(n + 1)]
for _ in range(n):
v, *edges = map(int, input().split())
for w in edges:
if w != -1:
tree[v].append(w)
tree[v].sort()
root = int(input())
left = [0] * (n + 1)
right = [0] * (n + 1)
order = 0
dfs(root)
for i in range(1, n + 1):
print(i, end=" ")
print(left[i], end=" ")
print(right[i])
'Python > Coding Test' 카테고리의 다른 글
22943 수 (0) | 2022.03.01 |
---|---|
4803 트리 (0) | 2022.03.01 |
22871 징검다리 건너기 (large) (0) | 2022.02.27 |
22869 징검다리 건너기 (small) (0) | 2022.02.27 |
1863 스카이라인 쉬운거 (0) | 2022.02.26 |