[백준] 1991 트리 순회 (Python 파이썬)

문제 설명

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

1991번: 트리 순회

 

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

---

풀이 과정

이 문제를 풀기 위해선, 전위 순회(preorder)와 중위 순회(inorder), 후위 순회(postorder)가 무엇인지에 대해 알고있어야 한다.

 

해당 이름들은 루트를 기준으로 이름이 붙여졌는데,

루트를 가장 먼저 방문하여 루트 -> 왼쪽자식 -> 오른쪽 자식을 방문하면 전위(preorder) 순회

루트를 중간에 방문하여 왼쪽자식 -> 루트 -> 오른쪽 자식을 방문하면 중위(inorder) 순회

루트를 마지막에 방문하여 왼쪽자식 -> 오른쪽자식 -> 루트를 방문하면 후위(postorder) 순회 이다.

 

이를 이용해 재귀문을 돌리면 된다.

위 그림과 같은 경우에는 

• 전위 순회 : A -> B -> D -> C -> E -> F -> G
• 중위 순회 : D -> B -> A -> E -> C -> F -> G 
• 후위 순회 : D -> B -> E -> G -> F -> C -> A 으로 나타난다.

전위순회를 예로 들자면 초기 루트인 A를 가장 먼저 방문하고,

A의 왼쪽자식들을 모두 방문한 후에 오른쪽 자식들을 방문하므로 위와 같은 결과가 나온다.

 

이 때, A가 왼쪽 자식들을 모두 방문하기 전에 오른쪽 자식들을 방문하지 않기 위해선

즉, A의 왼쪽을 모두 방문하고 나서야 B를 방문하기 위해선

A의 왼쪽 자식먼저 깊이우선 탐색을 실행해야 할것이다.

따라서 재귀문으로 실행시켜주면 된다.

 

트리는 파이썬의 딕셔너리를 이용하는 방법이 있고

리스트를 이용하는 방법이 있는데,

 

이번 풀이는 리스트를 이용해 아스키코드를 계산해주어 각 알파벳에 맞는 칸에 트리의 원소들을 넣어주었다.

(딕셔너리를 이용한 풀이가 좀 더 간결하니 두 방법 모두 시도해보는 것을 추천한다.)

n = int(input())

graph = [[[] for _ in range(2)] for _ in range(26)]


def pre_order(root):
    print(chr(root + ord('A')), end='')
    if graph[root][0]:
        pre_order(graph[root][0][0])
    if graph[root][1]:
        pre_order(graph[root][1][0])

def in_order(root):
    if graph[root][0]:
        in_order(graph[root][0][0])
    print(chr(root + ord('A')), end='')
    if graph[root][1]:
        in_order(graph[root][1][0])

def post_order(root):
    if graph[root][0]:
        post_order(graph[root][0][0])
    if graph[root][1]:
        post_order(graph[root][1][0])
    print(chr(root + ord('A')), end='')

for i in range(n):
    a, b, c = input().split()

    if b != ".":
        graph[ord(a) - ord('A')][0].append(ord(b) - ord('A'))
    if c != ".":
        graph[ord(a) - ord('A')][1].append(ord(c) - ord('A'))


pre_order(0)
print()
in_order(0)
print()
post_order(0)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !