5. Tree 전위순회 중위순회 후위순회 (백준 1991 파이썬)

트리도 오랜만이다.. 실버 1인데 반해 정답률도 높고 어렵지 않은 문제이지만, 혼자 잘 풀어낸 기념으로 작성

문제에 사실상 개념이 다 적혀있지만

• 이진 트리 : 한 노드에 자식 노드가 최대 2개인 트리
• 전위 순회(preorder) : 루트 -> 왼쪽 자식 -> 오른쪽 자식
• 중위 순회(inorder) : 왼쪽 자식 -> 루트 -> 오른쪽 자식
• 후위 순회(postorder) : 왼쪽자식 -> 오른쪽자식 -> 루트

 

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

1991번: 트리 순회

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

---

접근법 

• 사람에 따라 다르겠지만 나는 dict() 자료형에 담아 사용했다. (처음에 순서대로 주는 줄 알고 ord('A') 썼다가 큰 코 다쳤음...) 순서 상관 없다면 딕셔너리 넘 편해여
• 핵심은 재귀 사이에서 print()를 어느 순서에서 하는지 - 다른 분들 코드에서는 더 보기 분명하기는 했지만..ㅎ
• 아쉬운 점 : '.'인지 여부 체크를 한번만 할 수 있었을 거 같긴 한데.. 일단 직관적으로 짠 결과는 이렇다.
• 그리고 지금 보니 중위순회를 아무 생각 없이 mid 썼네ㅎ inorder입니당

import sys
sys.stdin = open('1991.txt')

N = int(sys.stdin.readline())
T = dict()
for _ in range(N):
    a, b, c = sys.stdin.readline().split()
    if T.get(a):
        T[a] += [b]
        T[a] += [c]
    else:
        T[a] = [b]
        T[a] += [c]

def pre(V):
    print(V, end='')
    temp = T[V]
    if temp[0] == '.' and temp[1] == '.':
        return
    if temp[0] != '.':
        pre(temp[0])
    if temp[1] != '.':
        pre(temp[1])


def mid(V):
    temp = T[V]
    if temp[0] == '.' and temp[1] == '.':
        print(V, end='')
        return
    if temp[0] != '.':
        mid(temp[0])
    print(V, end='')
    if temp[1] != '.':
        mid(temp[1])


def post(V):
    temp = T[V]
    if temp[0] == '.' and temp[1] == '.':
        print(V, end='')
        return
    if temp[0] != '.':
        post(temp[0])
    if temp[1] != '.':
        post(temp[1])
    print(V, end='')

pre('A')
print()
mid('A')
print()
post('A')

트리 제일 기본 문제도 끝~

내일 목표는 각종 정렬 마스터와(특히 제일 기본 선택정렬이랑 퀵정렬..) 분할정복? 그리고 브루트포스(순열, 비트마스크) 유형.. 다 할 수 있을까~