[BOJ][Python]1991번 풀이

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

1991번: 트리 순회

from string import ascii_uppercase
import sys
ssr = sys.stdin.readline

def preorder(v):
    global ans
    if visited[v] == 1:
        return
    visited[v] = 1
    ans += str(v)
    for i in edges:
        if i[0] == v:
            for j in range(1,3):
                if i[j] != '.':
                    preorder(i[j])

def inorder(v):
    global ans
    if visited[v] == 2:
        return
    visited[v] = 2
    for i in edges:
        if i[0] == v:
            if i[1] != '.':
                inorder(i[1])
            ans += i[0]
            if i[2] != '.':
                inorder(i[2])
            
def postorder(v):
    global ans
    if visited[v] == 3:
        return
    visited[v] = 3
    for i in edges:
        if i[0] == v:
            for j in range(1,3):
                if i[j] != '.':
                    postorder(i[j])
            ans += i[0]
                    
n = int(ssr())
edges = [ssr().rstrip().split() for _ in range(n)]
visited = {i:0 for i in ascii_uppercase}
ans = ''

preorder('A')
print(ans)
ans = ''

inorder('A')
print(ans)
ans = ''

postorder('A')
print(ans)
ans = ''

사실 저는 전위 순회니, 중위 순회니, 후위 순회니 하는 말을 오늘 처음 들어서 약간 난해하긴 했는데 전위 순회는 늘 하던 dfs와 같았고, 중위 순회와 후위 순회가 좀 독특했네요. 그래도 막 어렵지는 않았습니다.

 

문제 접근은 재귀입니다. 언제 노드를 출력하는지 타이밍만 조절하면 되는 문제였어요. 탐색을 하는 순서 자체는 다르지 않았던 것 같은 느낌입니다(이 부분은 제가 틀렸을 수도 있습니다). 우리가 일반적으로 하던 그래프 탐색을 그대로 진행해주시면 되고, 저 같은 경우는 조금 코드를 수월하게 짜기 위해서 string 라이브러리를 가져와서 upperscale 알파벳을 key로 갖는 딕셔너리를 만들었습니다. 숫자는 인덱스를 그대로 사용해도 되지만 해당 문제는 노드를 알파벳으로 주다 보니 해당 방법은 사용하지 못하겠죠. 그 외에는 크게 어려울만한 점이 없는 것 같네요. 약간 헷갈렸던 부분은 중위 순회의 왼쪽 - 루트 - 오른쪽의 말이 조금 헷갈렸습니다. 루트는 트리에서 맨 위에 있는 정점 하나인데 그럼 왼쪽의 모두를 다 돌고 루트를 출력하는지 아니면 왼쪽 - 부모 - 오른쪽 순으로 출력하는지 둘 중에서 뭐가 정답인지 잘 몰라서 검색을 했었네요. 검색해본 바로는 왼쪽 - 부모 - 오른쪽의 순서가 맞았습니다.