[Python/백준] 1991. 트리 순회

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

이진 트리의 순회

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

---

풀이

유니코드 풀이

import sys
input = sys.stdin.readline

# 입력 : 첫째 줄) 노드 개수
# 둘째 줄부터) N개 줄에 걸쳐 노드 이름, 레프트 자식 노드, 라이트 자식 노드 이름
# 각 노트 이름은 'A', 'B', ..., 'Z' 까지.
# 자식 노드가 없는 경우는 .으로 표기함.

def ord_minus_ord(x):
    return ord(x) - ord('A')
def chr_plus_ord(x):
    return chr(x + ord('A'))

def preorder(node):
    # node에는 0, 1, ..., 25가 들어감.
    if node == ord_minus_ord('.'):
        return
    print(chr_plus_ord(node), end = '')
    preorder(tree[node][1])
    preorder(tree[node][2])

def inorder(node):
    # node에는 0, 1, ..., 25가 들어감.
    if node == ord_minus_ord('.'):
        return
    inorder(tree[node][1])
    print(chr_plus_ord(node), end = '')
    inorder(tree[node][2])

def postorder(node):
    # node에는 0, 1, ..., 25가 들어감.
    if node == ord_minus_ord('.'):
        return
    postorder(tree[node][1])
    postorder(tree[node][2])
    print(chr_plus_ord(node), end = '')

n = int(input())

tree = [list(map(ord_minus_ord, input().split())) for _ in range(n)]
# 여기서, 이 tree 입력은 알파벳순이 아니므로, 정렬해줘야함.
tree.sort(key = lambda x:x[0])

preorder(ord_minus_ord('A'))
print()
inorder(ord_minus_ord('A'))
print()
postorder(ord_minus_ord('A'))

유니코드 풀이로 맞긴 했지만,

솔직히 사용자 정의 함수를 썼음에도 불구하고 너무 난잡하고 실수하기 쉬움.

근데, 막상 풀라고 하면 이렇게 못 풀것도 없어보임.

tree를 지금은 원형 그대로 받아놨지만, 미리 tree를 [-1, -1]로 초기화 시켜놓고, 그 담에 ‘.’가 아닐 때만 대입하는 방식으로 풀어도 가능.

딕셔너리 풀이

import sys
input = sys.stdin.readline

def preorder(node):
    # node에는 'A', ...이 들어감
    if node == '.':
        return
    print(node, end = '')
    preorder(alpha_dict[node][0])
    preorder(alpha_dict[node][1])

def inorder(node):
    # node에는 'A', ...이 들어감
    if node == '.':
        return
    inorder(alpha_dict[node][0])
    print(node, end = '')
    inorder(alpha_dict[node][1])

def postorder(node):
    # node에는 'A', ...이 들어감
    if node == '.':
        return
    postorder(alpha_dict[node][0])
    postorder(alpha_dict[node][1])
    print(node, end = '')

n = int(input())
# 'A' : ['B', 'D'] 꼴을 만들고 싶음.

alpha_dict = {}
for _ in range(n):
    parent, *alpha_dict[parent] = input().split()

# 이거 사실 알파벳이 같이 안 들어왔어도, 그냥 유니코드 적당히 써서 구현 가능.

preorder('A')
print()
inorder('A')
print()
postorder('A')

 

음, 나는 실전이라면 딕셔너리 풀이로 풀 것 같은데?

구현은 좀 복잡할 수 있어도, 더 간결하고 실수할 가능성이 낮음

이거 말고도 가능한 풀이 방법은 많음.

일단 리스트로 다 받고, 첫 번째 원소 기준으로 sort해서 ABC… 순서로 리스트 되게 한 다음에, ㅇ

그걸로 유니코드 쓸 수도 있겠고, …

아님, 그냥 {’A’ : ‘0’, … } 이런 딕셔너리를 만들고, 딕셔너리 인덱싱으로 재귀 돌려도 될거임.

저 딕셔너리 자체는 그냥 리스트 2개 해서 zip 한다음 해도 되겠고, 방법은 많겠지.

딕셔너리 풀이가 더 깔끔해보임.

(이진) 트리를 입력받을 때, 노드 번호가 순차적인 숫자가 아니면 딕셔너리로 트리를 정의하는 테크닉!! 기억하자.

---

250225 재풀이

import sys
input = sys.stdin.readline

# 노드 개수 n
# 그 다음부터 노드 정보들
# 부모, 왼쪽 자식 노드, 오른쪽 자식 노드
# 이진 트리
n = int(input())
tree = {}
for _ in range(n):
    parent, *tree[parent] = input().split()

def preorder(node):
    # 1. 깡통 노드면 종료
    if node == '.':
        return
    # 2. 그렇지 않으면, 해당하는 순회 action 실행
    print(node, end = '')
    preorder(tree[node][0])
    preorder(tree[node][1])

def inorder(node):
    # 1. 깡통 노드면 종료
    if node == '.':
        return
    # 2. 그렇지 않으면, 해당하는 순회 action 실행
    inorder(tree[node][0])
    print(node, end = '')
    inorder(tree[node][1])

def postorder(node):
    # 1. 깡통 노드면 종료
    if node == '.':
        return
    # 2. 그렇지 않으면, 해당하는 순회 action 실행
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end = '')


preorder('A')
print()
inorder('A')
print()
postorder('A')