[python] 백준 22856 트리 순회

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

22856번: 트리 순회

 

문제 해결

• 트리의 간선 지나간 횟수를 셀 수 있는가 문제
• 전체 이동하고 왕복했을 때 지나간 간선 개수 - 오른쪽으로만 이동했을 때 끝까지 간 편도 간선 개수
• DFS를 이용해 간선의 개수를 세는 것이 편하다.
• 자식 노드는 최대 두 개이다. (1개 일 때는 오른쪽 노드를 -1로 정의)

 

CODE

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs1(node):
    global cnt
    visited[node] = True
    
    if not visited[Tree[node][0]] and Tree[node][0] != -1:
        dfs1(Tree[node][0])
        cnt += 1
    if not visited[Tree[node][1]] and Tree[node][1] != -1:
        dfs1(Tree[node][1])
        cnt += 1

def dfs2(node):
    global cnt2
    visited[node] = True
    
    if not visited[Tree[node][1]] and Tree[node][1] != -1:
        dfs2(Tree[node][1])
        cnt2 += 1
        

if __name__=='__main__':
    n = int(input())
    Tree = {}
    for i in range(n):
        a, b, c = map(int, input().split())
        Tree[a] = [b,c]
    visited = [False]*(n+1)
    cnt = 0
    dfs1(1)
    cnt2 = 0
    visited = [False]*(n+1)
    dfs2(1)
    print(2*cnt-cnt2)