백준 22856 : 트리 순회 (Python)

본문 링크

"""
모든 노드들의 길이를 구한다음에
오른쪽만 이동한 거리를 빼준다.


 루트 노드는 항상 1번 노드이다.
"""
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS1(Node):
    global count
    visit[Node]=True

    if not visit[Tree[Node][0]] and Tree[Node][0]!=-1:
        DFS1(Tree[Node][0])
        count += 1
    if not visit[Tree[Node][1]] and Tree[Node][1]!=-1:
        DFS1(Tree[Node][1])
        count += 1

def DFS2(Node):
    global count2
    visit[Node]=True

    if not visit[Tree[Node][1]] and Tree[Node][1]!=-1:
        DFS2(Tree[Node][1])
        count2 += 1
N=int(input())
Tree={}

for i in range(N):
    a,b,c=map(int,input().split())
    Tree[a]=[b,c]

visit=[False]*(N+1)
count=0
DFS1(1)
count2=0
visit=[False]*(N+1)
DFS2(1)

print(2*count-count2)

📌 어떻게 접근할 것인가?

잘 생각해보자. 문제에서 주어지는 그림에서 오로지 한방향으로만 이동하는 지점이 어디인가?

바로 중위순회의 끝 이다.
즉 항상 오른쪽으로 가는 지점에 대해서는 오로지 한번씩만 방문한다.

총 2번의 $DFS$ 를 사용하였다.

첫번째 $DFS$ 는 단순히 모든 노드들을 이동하면서 거리를 구한다.

두번째 $DFS$ 는 오로지 오른쪽으로만 이동한다.

따라서 첫번째로 구한 값을 count 라고 하고 두번째로 구한 값을 count2 라고 하였을때

2*count-count2 가 정답이 된다.