[BOJ_4256] 트리

4256번: 트리

 

✅ 문제 설명

이진 트리의 전위순회, 중위순회 결과가 주어졌을 때, 후위 순회의 결과를 유추하는 문제입니다.

이때, 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어집니다.

 

✅ 접근 방식

문제 풀기 전에 끄적였던 것.

 

---

저번 포스팅이었던 이진 검색 트리에서 썼던 로직과 같은 로직을 이용했습니다. (참고)

[BOJ_5639] 이진 검색 트리 (python)

 

위의 문제는 이진 검색 트리에서의 전위순회 결과가 주어졌을 때, 후위순회 결과를 알아내는 것이었습니다.

이번 문제는 이진 트리에서의 전위순회와 중위순회가 주어졌을 때, 후위순회 결과를 알아내는 문제입니다.

 

이진 검색트리에서는 루트보다 작은 값은 왼쪽 서브트리로, 루트보다 큰 값은 오른쪽 서브트리로 나눠졌기 때문에 전위 순회 결과만 있으면, 루트와, 왼쪽서브트리, 오른족 서브트리의 노드값을 구분할 수 있었습니다.

• 전위 순회는 (루트)(왼쪽)(오른쪽) 순이니까 제일 처음 값이 루트이고 루트값보다 큰 값이 나오는 순간부터는 오른쪽 서브트리

 

근데 이번 문제에서는, 이진 검색트리가 아니라 일반 이진 트리였기 때문에 전위순회, 중위순회 두개의 결과를 이용합니다.

위에서 "문제 풀기 전에 끄적였던 것"에도 나와있듯이 전위순회는 (루트)(왼쪽)(오른쪽)으로 순회하기 때문에 가장 처음 나오는 값이 루트가 됩니다. 따라서 루트를 찾기 편합니다! 따라서 전위 순회를 통해 루트값을 찾기로 합시다.

 

전위 순회에서 루트 값을 찾았으면, 이 값을 이용해 (왼쪽)(오른쪽)을 나눌 수 있습니다.

어떻게 나눌까요? 중위 순회에서는 루트가 나오기 전까지의 값들은 왼쪽 서브트리의 구성요소가 됩니다. 이 값이 몇 개가 되는 지를 세어서 전위순회를 (루트)(***) -> (루트)(왼쪽)(오른쪽)으로 나눠볼 수 있습니다. 

만약 중위 순회에서 루트가 나오기 전 값들이 3개 였다면, 전위순회에서 첫값인 루트를 빼고 다음의 3개는 (왼쪽)에 해당, 그 이후는 (오른쪽)에 해당합니다.

 

즉 왼쪽 서브트리와 오른쪽 서브트리를 나눌 수 있는 기준이 생긴 것입니다!

 

boj_5639문제에서 (왼쪽),(오른쪽)을 나누는 기준이 루트값 보다 큰 지 작은 지였다면, 이 문제에서는 위처럼 구분하면 되는 것입니다. 이 부분의 로직만 바꿔서 전위순회의 결과를 이용해 후위순회를 진행하였고 결과를 얻을 수 있었습니다!

 

✅ 코드 설명

def postorder(start, end, s, e):
    if start > end:
        return
    if s > e:
        return

    root = preorder[start]

    left_len = 0
    for i in range(s, e + 1):  # start+1부터 end까지
        if int(root) == inorder[i]:  # 중위 순회 결과에서 루트가 나오면 그 전까지가 왼쪽 서브트리다.
            break
        left_len += 1

    postorder(start + 1, start+left_len, s, s+left_len-1)
    postorder(start+left_len+1, end, s+left_len+1, e)
    answer.append(root)

후위 순회 로직은 위처럼 구성했습니다. 전위순회 결과 배열만을 이용해 후위순회를 했던 boj_5639와는 달리 전위순회, 중위순회 결과 배열을 모두 봐야하므로 인자를 start, end, s, e로 구성하였습니다.

• start, end: 전위순회 결과를 저장한 배열(preorder)에 접근하기 위한 시작인덱스, 끝인덱스
• s, e: 중위순회 결과를 저장한 배열(inorder)에 접근하기 위한 시작인덱스, 끝인덱스

이처럼 인덱스를 넘겨주는 이유는 서브트리에 해당하는 노드들의 리스트를 넘겨주지 않고 시작과 끝 인덱스를 넘겨주어 같은 리스트를 재활용하기 위함입니다.

---

이제 함수 안을 살펴보면,

시작인덱스는 끝인덱스를 넘어갈 수 없으므로, start> end거나 s>e이면 종료합니다.

루트값은 전위순회한 결과의 첫번째 값이 되므로 preorder[start]를 통해 알 수 있습니다. 

 

왼쪽 서브트리에 해당되는 노드의 개수를 구하기 위해,

중위순회 결과값을 for문으로 탐색하면서 루트값이 나오기 전까지의 수를 카운팅해 left_len에 저장합니다.

그러면 전위순회 결과에서 루트 이후 left_len개의 노드는 왼쪽 서브트리, 그 이후는 오른쪽 서브트리에 해당합니다.

 

이를 이용해 다음과 같이 후위 순회를 시행하는데,

1) postorder(start + 1, start+left_len, s, s+left_len-1)를 통해 왼쪽 서브트리를 탐방

2) postorder(start+left_len+1, end, s+left_len+1, e)를 통해 오른쪽 서브트리를 탐방

3) answer.append(root)를 통해 루트값을 정답 배열에 저장

결과적으로 (왼쪽)(오른쪽)(루트)순으로 정답배열에 값이 저장되게 됩니다.

 

T = int(sys.stdin.readline())
answers = []
for _ in range(T):
    n = int(sys.stdin.readline())
    answer = []
    preorder = list(map(int, sys.stdin.readline().split()))
    inorder = list(map(int, sys.stdin.readline().split()))

    postorder(0, n-1, 0, n-1)
    answers.append(answer)

테스트의 개수 T 동안 반복합니다.

전위순회, 중위순회 결과를 받아 각각 리스트 preorder, inorder에 저장하고, 위에서 정의한 postorder를 수행합니다. 이때 postorder함수의 인자로는 시작 끝 인덱스를 0과  n-1로 주어, preorde과 inorder배열의 전체를 넘겨주었습니다.

 

✅ 최종 코드

# 트리

import sys


def postorder(start, end, s, e):
    if start > end:
        return
    if s > e:
        return

    root = preorder[start]

    left_len = 0
    for i in range(s, e + 1):  # start+1부터 end까지
        if int(root) == inorder[i]:  # 중위 순회 결과에서 루트가 나오면 그 전까지가 왼쪽 서브트리다.
            break
        left_len += 1

    postorder(start + 1, start+left_len, s, s+left_len-1)
    postorder(start+left_len+1, end, s+left_len+1, e)
    answer.append(root)


T = int(sys.stdin.readline())
answers = []
for _ in range(T):
    n = int(sys.stdin.readline())
    answer = []
    preorder = list(map(int, sys.stdin.readline().split()))
    inorder = list(map(int, sys.stdin.readline().split()))

    postorder(0, n-1, 0, n-1)
    answers.append(answer)

for i in answers:
    print(*i)

 

❇️ 코멘트

• 문제를 보자마자 boj_5639같은 방식으로 풀면 되지 않을까? 가 생각이 바로 났으나 뭔가 선뜻 기억나지 않아서 다시 복기하면서 풀었습니다 ㅎㅎ 그래도 덕분에 다시 문제를 돌아볼 수 있어서 좋았습니다. 
• 그래도 트리문제만 연속으로 푸니, 이제 어느정도 트리에 대한 감이 잡혀가는 것 같아서 좋다고 생각합니다.
• 왼쪽 서브트리와 오른쪽 서브트리를 나눌 수 있는 기준을 찾는 게 핵심이었던 것 같습니다.
• 혹시 인덱스값이 왜 저렇게 됐는지 이해가 안되시면 댓글 남겨주세요!