트리순회: 백준 1991번 오답노트

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

본 글은 위 백준 알고리즘 문제를 풀며 정리한 글입니다.

---

1. 문제 개요

• 입력:
  첫 줄에 노드의 개수 (N)이 주어지고, 이후 (N)개의 줄에 각 노드와 그 노드의 왼쪽, 오른쪽 자식이 주어진다. 이때 자식이 없으면 점('.')으로 표현됨.

• 출력:
  전위 순회, 중위 순회, 후위 순회 결과를 각각 한 줄에 출력

• 예제 트리 (입력 예시):

    A
   / \
  B   C
 /   / \
D   E   F
         \
          G

• 순회 방법:
  • 전위 순회: 루트 → 왼쪽 → 오른쪽
  • 중위 순회: 왼쪽 → 루트 → 오른쪽
  • 후위 순회: 왼쪽 → 오른쪽 → 루트

---

2. 풀이

import sys
input = sys.stdin.readline

# 트리 정보를 저장할 딕셔너리 생성 (key: 노드, value: (왼쪽 자식, 오른쪽 자식))
tree = {}

# 노드의 개수 입력
N = int(input().strip())

# 각 노드와 자식 정보를 입력받아 딕셔너리에 저장
for _ in range(N):
    root, left, right = input().split()
    tree[root] = (left, right)

# 전위 순회: 루트 -> 왼쪽 -> 오른쪽
def preorder(node):
    if node == '.':
        return ""
    return node + preorder(tree[node][0]) + preorder(tree[node][1])

# 중위 순회: 왼쪽 -> 루트 -> 오른쪽
def inorder(node):
    if node == '.':
        return ""
    return inorder(tree[node][0]) + node + inorder(tree[node][1])

# 후위 순회: 왼쪽 -> 오른쪽 -> 루트
def postorder(node):
    if node == '.':
        return ""
    return postorder(tree[node][0]) + postorder(tree[node][1]) + node

# A가 루트 노드임을 이용하여 결과 출력
print(preorder('A'))
print(inorder('A'))
print(postorder('A'))

---

3. 코드 설명

1. 입력 및 트리 구성:

   • 각 노드 정보를 읽어들여, 딕셔너리 tree에 저장한다.
     예를 들어, 입력 A B C는 tree['A'] = ('B', 'C')와 같이 저장됨.

2. 재귀함수를 이용한 순회:

   • preorder(node): 현재 노드를 먼저 방문하고, 왼쪽 자식, 오른쪽 자식 순으로 방문
   • inorder(node): 왼쪽 자식을 먼저 방문한 후, 현재 노드를 방문하고, 마지막에 오른쪽 자식을 방문
   • postorder(node): 왼쪽 자식과 오른쪽 자식을 먼저 방문하고, 마지막에 현재 노드를 방문
   • 자식 노드가 없으면(즉, node == '.') 빈 문자열을 반환

3. 출력:

   • 루트 노드는 항상 A이므로 preorder('A'), inorder('A'), postorder('A')를 호출하여 결과를 출력하면 끝!

예제 입력의 경우

• 전위 순회: ABDCEFG
• 중위 순회: DBAECFG
• 후위 순회: DBEGFCA
  와 같이 출력됨.

4. 후기...

솔직히 어떻게 푸는지 감도 안 온 것이 전위 순회 중위 순회 후위 순회 이런 말을 여기서 처음 들었다... 입력 받는것부터 해서 이거 뭐 linked list 처러 만들어야하나? dictionary 양방향으로 통하게끔 뭐 만들어야하나? 이런생각 많이 했는데, 결국 몰라서 해설을 봤다...

하... 그런데 코드가 너무 간단하다... 아름답다 그냥
알고리즘 풀이를 하면서 느끼는건데
코딩을 잘한다는 건 뭐 엄청 머리가 비상하고 함수를 많이알고 이런게 아니라 자신의 추상화 된 개념을 어떻게 실제에서 구현 시킬지에 대해 명확히 알고있는 것을 의미하는 것 같다.

코드 봐라... 진짜 깔끔하다 그냥
dictionary로 받고 (여기까지는 트리니까 하겠는데)
별거 없다. 그냥 함수 선언해서 노드 들어오면 해당 노드가 . 으로 끝나는거 아닌 이상 말 그대로
전위 순회면 루트 + 왼 + 오 이렇게 return해주고

중위면 왼 + 루트 + 오
후위면 왼 + 오 + 루트 이렇게 return 해주면 끝이다.

return 된 값들에 전위 중위 후위에 관한 함수가 이미 포함되어 있으므로 return 절 안에서 다시 return이 이루어지며 순회하게 된다.
캬 ...

감탄이다 그냥...
나도 내가 추상화한 개념을 이렇게 깔끔하게 코드로 구현하고 싶다.
많이 노력해야겠다 정말