백준 22586 [트리 순회] 파이썬

https://www.acmicpc.net/problem/22856

#백준 22856 트리 순회

import sys
sys.setrecursionlimit(10**6)  # 재귀 깊이 제한을 늘려줌 (트리 깊이가 깊을 수 있으므로)
input = sys.stdin.readline

N = int(input())  # 노드의 개수 입력

LEFT = 0
RIGHT = 1
ans = 0  # 전체 dfs 순회에서 방문 기록용 카운터

# 트리 정보를 저장할 리스트. 각 인덱스에 대해 [왼쪽 자식, 오른쪽 자식]을 저장
trees = [[-1, -1] for _ in range(N+1)]

# 노드별로 왼쪽, 오른쪽 자식 정보를 입력받음
for _ in range(N):
    curr, left_leaf, right_leaf = map(int, input().split())
    trees[curr][LEFT] = left_leaf
    trees[curr][RIGHT] = right_leaf

# DFS로 트리 탐색을 수행
def dfs(node):
    global ans
    ans += 1  # 현재 노드 방문 시 카운트 증가

    # 왼쪽 자식이 존재하면 재귀적으로 방문 후 다시 카운트 증가
    if trees[node][LEFT] != -1:
        dfs(trees[node][LEFT])
        ans += 1  # 자식 노드에서 돌아온 뒤 다시 부모 노드로 돌아오는 비용

    # 오른쪽 자식이 존재하면 재귀적으로 방문 후 다시 카운트 증가
    if trees[node][RIGHT] != -1:
        dfs(trees[node][RIGHT])
        ans += 1  # 마찬가지로 돌아오는 비용

# 오른쪽으로만 내려가며 깊이를 측정하는 함수
def find_right_depth(node):
    if trees[node][RIGHT] == -1:
        return 1  # 더 이상 오른쪽 자식이 없으면 깊이 1로 종료
    else:
        return find_right_depth(trees[node][RIGHT]) + 1  # 오른쪽 자식 존재 시 깊이 +1하며 재귀 호출

dfs(1)  # 루트 노드(1번 노드)부터 DFS 시작

# 전체 이동 횟수(ans)에서 마지막 오른쪽 리프 노드에서 돌아오는 횟수는 빼줌
print(ans - find_right_depth(1))