[BOJ] 22856. 트리 순회 (🥇, 트리)

🔗

풀이

중위 순회인데 이제 모든 노드를 탐색하면 도중에 중단해야 한다는 조건이 있다.

이때 주의해야 할 점은 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서대로 방문처리를 해야 한다는 점이다. 부모 노드에 들어가자마자 방문 처리를 하게 되면 왼쪽 자식 노드를 방문한 후에 다시 부모 노드로 되돌아올 수 없다.

그림 처럼 6을 방문한 후에는 3으로 다시 되돌아 가야 한다. 하지만 3에서 1로 다시 되돌아가지는 않는다. 3은 1의 오른쪽 자식 노드이기 때문에 이미 1은 방문처리가 되어 있어 유사 중위 순회가 종료되었기 때문이다.

# 트리 순회

import sys
sys.setrecursionlimit(1000000)

def traversal(i, cnt):
    if tree[i][0] != -1:
        cnt = traversal(tree[i][0], cnt+1) + any(visited)
    visited[i] = False
    if tree[i][1] != -1:
        cnt = traversal(tree[i][1], cnt+1) + any(visited)
    return cnt
N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N):
    a, *child = map(int, input().split())
    tree[a].extend(child)

visited = [True] * (N+1)
visited[0] = False
print(traversal(1, 0))