백준 1991 트리 순회 파이썬 문제풀이 (python 트리)

문제 보러가기

 

 

백준 트리 순회 파이썬 문제풀이

노드에 부모와 자식 계층이 있고,

순환하지 않는 형태로 연결된 모습을 트리라고 한다.

 

트리를 순회하는 방법에는

전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)

이렇게 세 가지가 있다.

 

이번 문제에는 입력으로 자식이 최대 2개만 있는 이진트리를 받게 되는데

이진 트리를 순회하는 세 가지 방법으로 출력된 결과를 뽑는 문제이다.

 

하지만 전위, 중위, 후위는 따로 생각하지 않아도 된다.

이유는 코드를 보도록 하자.

 

n = int(input())

graph = [[] for _ in range(130)]

for _ in range(n):
    a,b,c = map(str, input().split())
    # ASCII code
    a = ord(a)
    b = ord(b)
    c = ord(c)

    graph[a].append(b)
    graph[a].append(c)

def recur(node):
    if node == 46:
        return

    print(chr(node), end="")
    recur(graph[node][0])
    recur(graph[node][1])

recur(65)

우선 이진트리의 루트인 A부터 시작하는 그래프를 만들었다.

여기서 알파벳을 key로 사용하기 위해서 아스키 코드를 사용하였다.

아스키 코드는 우리가 입력할 수 있는 알파벳이나 문자 등에 대해서 컴퓨터가 알아듣는 정수 형태의 코드이다.

 

A는 65이고, 없다는 뜻의 '.'은 46이다.

입력시 각각의 부모와 좌 우 자식들을 ASCII 코드를 키로 해서 넣어주고.

 

recur재귀 함수를 이용한다.

46은 '.' 즉 자식이 없다는 것이므로 정지신호.

 

    print(chr(node), end="")
    recur(graph[node][0])
    recur(graph[node][1])

여기서 중요한 것은 이 세 줄이다.

지금은 먼저 현재 노드를 출력하고,

좌, 우 자식노드로 각각 재귀하게 된다.

 

    recur(graph[node][0])
    print(chr(node), end="")
    recur(graph[node][1])

재밌는 것은 이 순서를 이렇게 바꾸면 중위가 되고 

 

    recur(graph[node][0])
    recur(graph[node][1])
    print(chr(node), end="")

이렇게 바꾸면 후위가 된다.

이게 뭔지 알겠는가?

 

바로 읽는 노드가 언제 배치되느냐에 따라서

전/중/후위 순회로 나뉘는 것이다.

 

정답코드

n = int(input())

graph = [[] for _ in range(130)]

for _ in range(n):
    a,b,c = map(str, input().split())
    # ASCII code
    a = ord(a)
    b = ord(b)
    c = ord(c)

    graph[a].append(b)
    graph[a].append(c)

preorder = []
inorder = []
postorder = []

def recur(node):
    if node == 46:
        return

    preorder.append(node)
    recur(graph[node][0])
    inorder.append(node)
    recur(graph[node][1])
    postorder.append(node)

recur(65)

for i in preorder:
    print(chr(i),end="")
print()
for i in inorder:
    print(chr(i),end="")
print()
for i in postorder:
    print(chr(i),end="")

이렇게 각각의 순회 방법을 저장해놓았다가 출력하면 

 

정답이다.

 

하나 알아두어야할 점은.

중위 순회의 경우 이진트리이기 때문에 가능한 구조이다.

 

전위와 후위는 읽는 노드가 맨 처음이나 맨 끝에 위치하지만,

중위 순회는 '중간'이라는 개념이 있어야하므로 자식 노드에 갯수에 따라 

달라질 수 있다.