[Python, 백준/1991번] 트리 순회

 

---

☑️ [Python, 백준/1991번] 트리 순회

1️⃣ 문제

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

예를 들어 위와 같은 이진 트리가 입력되면, 

전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 

중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 

후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 

가 된다.

 

2️⃣ 접근

문제 자체는 어렵지 않았다. 단순하게 Preorder, Inorder, Postorder 순서를 구하면 된다. 다만, 예제 데이터에서 트리 구조를 어떻게 만들지 고민이 있었다.

 

입력 예제는 다음과 같다.

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

 

첫번째 줄은 트리를 구성하는 Node의 개수를 알려주고, 이후에는 트리에 어떤 Node가 연결이 되어있는지 데이터를 전달해준다. 그렇기 때문에 처음에 들어온 값을 2차원 배열의 크기로 정해서 나머지 값을 입력 받으면 된다. 두번째 줄 이후, 0번째에 위치한 알파벳이 각 Node를 의미하고 이후 알파벳들은 Leap Node를 의미한다.

 

처음에는 0번째에 위치한 알파벳만 List를 만들어서 Node 자식에 접근하려고 시도 했는데 (Index * 2) + 1와 같은 Node 자식 접근 공식으로 접근되지 않음을 알았다.

 

그러면 방법은 2가지가 있다. Dictionary에 데이터를 저장해서 Key 값으로 Node가 가진 알파벳을 지정하는 방법과 Index를 찾아주는 메서드를 만들어서 사용하는 방법이 있다. Dictionary로 데이터를 삽입 후, 검색하는 방법으로 가면 각각 O(1)의 시간 복잡도를 가진다. 그렇기 때문에 위와 같이 접근하는게 효율적일 수 있다.

 

하지만 후자의 방법으로 Value를 넣어주면 해당 Value의 Index를 반환하는 메서드를 만들어서 사용했다. 시간도 충분하겠다 그냥 메서드를 만들어서 풀고 싶었다. 이제 남은 것은 순회한 내용을 출력하는 것인데, 이건 예전에 배운 적이 있어서 크게 어려움이 없었다.

 

전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 

 

또, 문제 설명에서 모든 것을 알려주고 있기 때문에 어려운 내용은 없었다. 전위, 중위, 후위 순회는 각자 메서드, print 메서드 사용 순서를 변경해주면 바로 풀 수 있다.

 

3️⃣ 코드

num = int(input())
tree_edge = [input() for _ in range(num)]

# Text를 추가해서 반환 값으로 해당 Text의 Index를 반환한다.
def find_index(text : str) -> int:    
    for i, item in enumerate(tree_edge):
        if item[0] == text:
            return i
    return -1

# Pre Order -> A B C
# In Order -> B A C
# Post Order -> B C A
def preorder(text : str):
    if text == '.':
        return
    
    result = find_index(text)
    if result == -1:
        return
    
    print(text, end = '')
    preorder(tree_edge[result][2])
    preorder(tree_edge[result][4])

def inorder(text : str):
    if text == '.':
        return
    
    result = find_index(text)
    if result == -1:
        return
    
    inorder(tree_edge[result][2])
    print(text, end = '')
    inorder(tree_edge[result][4])
    
def postorder(text : str):
    if text == '.':
        return
    
    result = find_index(text)
    if result == -1:
        return
    
    postorder(tree_edge[result][2])
    postorder(tree_edge[result][4])
    print(text, end = '')
    
preorder('A')
print('')
inorder('A')
print('')
postorder('A')