[백준 2263번] 트리의 순회 | python 풀이

---

 

📃백준 2263

🌲트리의 순회🌳

재귀, 분할 정복

 

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

 

---

백준 2263번 채점결과

 

 

 

---

 

 

 

🔷 SubMission Code

## 백준
## 2263번 : 트리의 순회
## 트리, 분할 정복, 재귀
##* 중위, 후위 => 전위순회

import sys
sys.setrecursionlimit(10**5)
##! 10**4(기본)로 하면 런타임 에러..
##! 10**6 이상 으로하면 메모리 초과가뜸..

def in_post_to_pre(in_l, in_r, post_l, post_r):
    if in_l > in_r or post_l > post_r:
        return
    root = post_order[post_r]
    mid = pos[root]
    # mid = in_order.index(root)
    left = mid - in_l
    right = in_r - mid
    print(root, end=" ")
    in_post_to_pre(in_l, in_l + left - 1, post_l, post_l + left - 1)
    in_post_to_pre(in_r - right + 1, in_r, post_r - right, post_r - 1)


if __name__ == "__main__":
    n = int(input())

    in_order = list(map(int, sys.stdin.readline().split()))
    post_order = list(map(int, sys.stdin.readline().split()))

    N = len(in_order)
    pos = [0] * (N + 1)

    for i in range(N):
        pos[in_order[i]] = i

    in_post_to_pre(0, N - 1, 0, N - 1)

백준 2263번 문제는 트리를 순회하는 방식인 전위 순회, 중위 순회, 후위 순회에 대한 개념을 이해하고 있어야 한다. 전위 순회는 루트, Left, Right 노드 순으로 트리를 순회하고, 중위 순회는 Left, 루트, Right 노드 순으로 트리를 순회한다. 마지막으로 후위 순회는 Left, Right, 루트 노드 순으로 트리를 순회한다. 이러한 특성을 이해하고 문제에 접근을 해야 한다. 문제는 입력으로 노드의 수와 중위 순회와 후위 순회가 주어진다. 이러한 입력 데이터를 활용해서 전위 순회를 출력시키면 되는 문제이다. 코드는 이전 포스팅인 4256번 트리 문제의 Reference code를 참고해서 만든 코드이다.

 

 

 

---

 

 

🔷 코드 흐름

##* 코드의 전체적인 흐름
import sys
sys.setrecursionlimit(10**5)

if __name__ == "__main__":
    n = int(input())

    in_order = list(map(int, sys.stdin.readline().split()))
    post_order = list(map(int, sys.stdin.readline().split()))

    N = len(in_order)
    pos = [0] * (N + 1)

    for i in range(N):
        pos[in_order[i]] = i

    in_post_to_pre(0, N - 1, 0, N - 1)

시스템 모듈인 sys를 import 해준다. sys는 인터프리터에 의해 사용되거나 유지되는 일부 변수와 인터프리터와 강하게 상호작용하는 함수에 대한 액세스를 제공하며 항상 사용이 가능하다. 메인 흐름을 보면 변수 n, in_order, post_order에 입력값을 받는다. 그리고 pos에 전위 순회로 사용될 리스트를 초기 세팅해준다. 전위 순회 리스트를 만들어서 리스트의 인덱스로 접근하는 방식과 중위 순회에서 index() 함수를 사용해서 접근하는 방식이 있는데 전자가 시간 428ms, 후자가 3116ms로 리스트의 인덱스로 직접 접근하는 게 효율적인 것을 확인할 수 있다.

 

 

 

 

---

 

 

🔶 참고!! sys 모듈

## 인터프리터가 표준 입력, 출력 및 에러에 사용하는 파일 객체

sys.stdin
sys.stdout
sys.stderr

• stdin는 모든 대화식 입력에 사용 (input() 호출을 포함)
• stdout은 print()와 표현식 문장의 출력과 input()의 프롬프트에 사용됨
• 인터프리터 자신의 프롬프트와 에러 메시지는 stderr로 감

 

 

 

 

 

🔶 sys.setrecursionlimit()

## 재귀함수 최대 깊이 핸들링

sys.getrecursionlimit()
sys.setrecursionlimit(limit)

재귀 문제를 풀 때 로컬인 vscode와 같은 에디터에서는 출력이 잘 되는데, 정작 문제 제출을 하면 에러를 접해봤을 것이다. 위에 채점 결과를 보면 런타임 에러와 메모리 초과 에러가 뜬 것을 볼 수 있는데 재귀의 최대 깊이를 기본적으로 설정을 해놓아서 이러한 에러가 발생하게 된다. 2263번 문제도 재귀를 이용한 풀이로 vscode에서는 정상적으로 예제 입력값을 넣었을 때 원하는 결과 출력을 얻을 수 있었는데 제출을 하면 런타임 에러가 떴다. 위의 코드로는 기본 깊이인 1000에서는 재귀 호출의 횟수가 더 많아서 뜨는 것이다. 그래서 처음에는 100000으로 재귀 최대 깊이를 sys.setrecursionlimit(10**6)으로 설정을 해줬다. 그럴 경우 메모리 초과 에러가 나왔다. 최대 깊이를 10**5으로 해주면 제출이 정상적으로 통과가 되었다. 이렇게 차이가 나는 이유가 궁금해서 파이썬 공식문서를 찾아보니 제한이 너무 높으면 충돌이 발생할 수 있기에 sys.setrecursionlimit를 사용할 때 주의하라고 나와있다. 

 

 

 

 

 

출처: python 공식문서

출처 : python 공식문서

 

 

 

 

---

 

 

 

 

🔶 전위 순회 결과 만들어주는 재귀함수

## 중위,후위 => 전위 순회 재귀함수

def in_post_to_pre(in_l, in_r, post_l, post_r):
    if in_l > in_r or post_l > post_r:
        return
    root = post_order[post_r]
    mid = pos[root]
    # mid = in_order.index(root)
    left = mid - in_l
    right = in_r - mid
    print(root, end=" ")
    in_post_to_pre(in_l, in_l + left - 1, post_l, post_l + left - 1)
    in_post_to_pre(in_r - right + 1, in_r, post_r - right, post_r - 1)

위에서 한번 언급했는데 pos[root]로 리스트 인덱스를 직접 넣어주는 경우와 in_order.index(root)로 index() 함수를 사용하는 방식이 있다. 두 개다 잘 동작은 하지만 위의 방식이 시간이 더 짧게 나오는 효율이 좋은 방식이다. 

 

 

 

 

 

 

🌲🌲🌳🌳🌳🌲🌲

 

 

 

 

 

 

 

소스 코드 링크 :

https://github.com/KwanHoo/Data-Structure__Algorithm/blob/main/Python/baekjoon/gold/Baek_2263.py

GitHub - KwanHoo/Data-Structure__Algorithm: Data structures and algorithms practice code, Backjoon submission code