| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 44171 | 28976 | 22150 | 66.595% |
문제
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
- 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
- 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
- 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
답안
from collections import defaultdict
import sys
def preorder_traversal(graph, start='A'):
left, right = graph[start]
print(start, end='')
if left is not None:
preorder_traversal(graph, left)
if right is not None:
preorder_traversal(graph, right)
return
def inorder_traversal(graph, start='A'):
left, right = graph[start]
if left is not None:
inorder_traversal(graph, left)
print(start, end='')
if right is not None:
inorder_traversal(graph, right)
return
def postorder_traversal(graph, start='A'):
left, right = graph[start]
if left is not None:
postorder_traversal(graph, left)
if right is not None:
postorder_traversal(graph, right)
print(start, end='')
return
input = sys.stdin.readline
graph = defaultdict(lambda: (None, None))
for _ in range(int(input())):
root, left, right = map(lambda x: None if x == '.' else x, input().split())
graph[root] = (left, right)
preorder_traversal(graph)
print()
inorder_traversal(graph)
print()
postorder_traversal(graph)풀이
이진 트리의 순회를 묻는 문제이다.
이진 트리는 어떤 노드 아래의 부분 트리도 모두 이진 트리이므로, 재귀를 이용해 간편하게 풀 수 있다.
input = sys.stdin.readline
graph = defaultdict(lambda: (None, None))
for _ in range(int(input())):
root, left, right = map(lambda x: None if x == '.' else x, input().split())
graph[root] = (left, right)입력을 받는 부분이다.
여기서 이진 트리를 저장하는 graph는 defaultdict로 선언하였다. defaultdict는 일반 파이썬 딕셔너리(dict)와 기능은 거의 같지만, 한 가지 추가된 것이 있다.
from collections import defaultdict
dict1 = dict([('A', 1), ('B', 2)])
print(dict1['A']) # 1
print(dict1['B']) # 2
print(dict1['C']) # KeyError: 'C'
dict2 = defaultdict(lambda: 0, [('A', 3), ('B', 4)])
print(dict2['A']) # 3
print(dict2['B']) # 4
print(dict2['C']) # 0위 예시와 같이, 일반 딕셔너리의 경우 키가 없는 값을 찾으려고 하는 경우 KeyError를 발생시키지만, defaultdict의 경우 이미 설정해놓은 기본값을 반환한다.
물론 일반 딕셔너리를 사용해도 문제를 풀 수 있지만, 불필요한 정보가 여럿 생기는 것을 방지하고자 defaultdict를 사용하였다.
def preorder_traversal(graph, start='A'):
left, right = graph[start]
print(start, end='')
if left is not None:
preorder_traversal(graph, left)
if right is not None:
preorder_traversal(graph, right)
return
def inorder_traversal(graph, start='A'):
left, right = graph[start]
if left is not None:
inorder_traversal(graph, left)
print(start, end='')
if right is not None:
inorder_traversal(graph, right)
return
def postorder_traversal(graph, start='A'):
left, right = graph[start]
if left is not None:
postorder_traversal(graph, left)
if right is not None:
postorder_traversal(graph, right)
print(start, end='')
return재귀를 통해 구현한, 각각 전위 순회, 중위 순회, 후위 순회이다. 세 개의 함수가 거의 비슷한 형태를 가지고 있다.
전위 순회는 루트 노드 - 왼쪽 노드 - 오른쪽 노드의 순서로 순회하므로, 왼쪽 노드와 오른쪽 노드를 순회하기 전 루트 노드를 출력하였다.
중위 순회는 왼쪽 노드 - 루트 노드 - 오른쪽 노드의 순서로 순회하므로, 왼쪽 노드를 모두 순회한 뒤 루트 노드를 출력하였고, 그 뒤 오른쪽 노드를 순회하였다.
후위순회는 왼쪽 노드 - 오른쪽 노드 - 루트 노드의 순서로 순회하므로, 가장 깊이 있는 왼쪽 노드와 오른쪽 노드까지 모두 순회한 뒤 루트 노드를 출력하였다.
위 재귀 함수에서 탈출 조건은 왼쪽과 오른쪽 자식 노드가 없을 때, 또는 왼쪽과 오른쪽 자식 노드 밑에 있는 부분 트리를 모두 순회했을 때이다.
출력하는 부분은 print(..., end='')와 같이 출력 형식을 지켜주었다.
preorder_traversal(graph)
print()
inorder_traversal(graph)
print()
postorder_traversal(graph)위와 같이 함수를 호출한 뒤 줄바꿈 문자를 출력하면 정답으로 인정된다.
