트리순회(백준 22856번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자.

순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다.

유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다.

1. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.
2. 그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로 이동한다.
3. 그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.
4. 그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.
5. 유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.

https://upload.acmicpc.net/ee01f435-9a8b-4d85-9720-4355f541fd4d/-/preview/

위 그림에 있는 트리에서 중위 순회를 한다면 4→2→5→1→6→3→7$4 \rightarrow 2 \rightarrow 5 \rightarrow 1 \rightarrow 6 \rightarrow 3 \rightarrow 7$ 순으로 순회를 한다.

따라서, 유사 중위 순회의 끝은 노드 7이 된다.

https://upload.acmicpc.net/c6cd786c-4235-499f-8ef2-57cdafd33ce7/-/crop/2544x1786/0,0/-/preview/

유사 중위 순회는 위 그림과 같이 루트인 노드 1$1$에서 시작하여 노드 7$7$에서 끝나고 1→2→4→2→5→2→1→3→6→3→7$1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7$ 이와 같은 순서로 순회를 진행한다. 유사 중위 순회를 진행하면서 총 10번 이동하였다.

여기서 이동이라는 것은 하나의 노드에서 다른 노드로 한번 움직이는 것을 의미한다. 예를 들면, 노드 1에서 노드 2로 가는 것을 한번 이동하였다고 한다.

유사 중위 순회를 하면서 이동한 횟수를 구하려고 한다.

나의 풀이(정답 참고)

import sys
sys.setrecursionlimit(10**6) 
def DFS_all(tree_dic,v):
    global count_a
    if v!=-1:
        count_a+=1
        DFS_all(tree_dic,tree_dic[v][0])
        DFS_all(tree_dic,tree_dic[v][1])

def DFS_right(tree_dic,v):
    global count_r
    if v!=-1:
        count_r+=1
        DFS_right(tree_dic,tree_dic[v][1])

N=int(input())
tree_dic=dict()
for _ in range(N):
    node,L,R=map(int,sys.stdin.readline().strip().split())
    tree_dic[node]=[L,R]
count_a=0
count_r=0
DFS_all(tree_dic,1)
DFS_right(tree_dic,1)
print(2*(count_a-1)-(count_r-1))

• 문제는 중위순회(inorder traversal)로 풀어야 하는 것처럼 하지만, 사실은 edge의 수를 세는 문제였다.
• 문제의 예시처럼 나오기 위해서는 간선의 개수를 세고, 2배를 해준 후, 오른쪽으로만 이동하는 간선의 개수를 빼주면 된다.(유사 중위 순회이기 때문에, 마지막에 다시 올라가지 않는다.)
• 여기서 주의할 점
  1. Edge의 개수는 Node개수-1이다.

  2. sys.setrecursionlimit(10**6) 꼭 필요하다.

     파이썬에서 recursion의 depth가 깊지 않기 때문에 오류가 발생한다.(이거 때문에 1시간동안 문제를 찾았다) 따라서 위와 같은 명령어 설정을 해주어야 정상적으로 동작한다. 코딩테스트에서도 위와 같은 사례가 꽤 있다고 함.