[백준] 1991번 : 트리 순회 ☆

유형 : 트리, 구현

[예시 입력]

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

[예시 출력]

ABDCEFG
DBAECFG
DBEGFCA

---

1. 내 풀이

N = int(input())

value_list = []
key_list = []
for _ in range(N):
    tmp = input().split(' ')
    key_list.append(tmp[0])
    value_list.append(tmp[1:])

graph = dict(zip(key_list,value_list))

start_node = 'A'
visited, need_visit = list(), list()
need_visit.append(start_node)

# 전위 순회
while need_visit:
    node = need_visit.pop()
    if node not in visited:
        if node == '.':
            continue
        visited.append(node)
        need_visit.extend(reversed(graph[node]))

print(visited)

visited, need_visit = list(), list()
need_visit.append(start_node)

▷ 어떻게 구현할 지 몰라서 전위 순회만 했다.

▷ 기본 유형인데.. 반성하자..

 

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

** 핵심 아이디어
1. 전위순회 : 루트 → 왼쪽 자식 → 오른쪽 자식
2. 중위순회 : 왼쪽 자식 → 루트 → 오른쪽 자식
3. 후위순회 : 왼쪽 자식 → 오른쪽 자식 → 루트

 

class Node:
    def __init__(self, data, left_node, right_node):
    	self.data = data
        self.left_node = left_node
        self.right_node = right_node

# 전위순회
def pre_order(node):
    print(node.data, end='')
    if node.left_node != '.':
    	pre_order(tree[node.left_node])
    if node.right_node != '.':
    	pre_order(tree[node.right_node])

# 중위순회
def in_order(node):
    if node.left_node != '.':
    	in_order(tree[node.left_node])       
    print(node.data, end='')
    if node.right_node != '.':
    	in_order(tree[node.right_node])

# 후위순회
def post_order(node):
    if node.left_node != '.':
    	post_order(tree[node.left_node])
    if node.right_node != '.':
    	post_order(tree[node.right_node])
    print(node.data, end='')
    
n = int(input())
tree = {}
for i in range(n):
    data, left_node, right_node = input().split()
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

 

 

문제 출처 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회