[백준] 1991번 트리 순회 (트리 문제)

사용 언어 - Python3

문제 -  1991번 트리 순회

트리 = Tree = 나무 = Root + Seed

족보(가족관계도) = 조상 + 자손

 

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

1991번: 트리 순회

 

정답

트리의 조건

1. 모든 노드들은 연결되어 있어야 한다. (1개도 트리 가능)

2. 사이클이 발생하면 안된다. (내 아들이 할아버지이다? 불가능)

 

트리의 종류

1. 조상이 정해진 트리 = 루티드 트리

2. 조상이 정해지지 않은 트리 = 트리

 

 

 

 

1. 문자열 <-> 아스키 코드

문자열 -> 아스키 코드

ord(A) = 65 이므로 -64를 해줘서 1로 만들어주기

 

아스키 코드 -> 문자열

chr(아스키코드+64)

 

2. DFS 재귀 함수로 구현하기

print(chr(start+64), end = "") 부모

tree[start][0] 왼쪽 자식

tree[start][1] 오른쪽 자식

 

3. print

항상 루트노트 = A = 1

preOrder(1)

print() 한줄 띄어쓰기

InOrder(1)

print() 한줄 띄어쓰기

postOrder(1)

 

# 전위 순회
def preOrder(start):
    if start != - 18:
        print(chr(start+64), end = "") # 부모
        preOrder(tree[start][0]) # 왼쪽 자식
        preOrder(tree[start][1]) # 오른쪽 자식
# 중위 순회
def inOrder(start):
    if start != -18:
        inOrder(tree[start][0]) # 왼쪽 자식
        print(chr(start+64), end = "") # 부모        
        inOrder(tree[start][1]) # 오른쪽 자식
# 후위 순회
def postOrder(start):
    if start != -18:
        postOrder(tree[start][0]) # 왼쪽 자식
        postOrder(tree[start][1]) # 오른쪽 자식       
        print(chr(start+64), end = "") # 부모

n = int(input()) # 노드 개수
tree = [[] for _ in range(n+1)] #아스키 코드 127까지 있음

for _ in range(n):
    a, b, c = input().split() # 노드, 왼쪽 자식, 오른쪽 자식
    # 노드 이름 A~ 알파벳 대문자라 탐색 어려우므로 아스키 코드로 변경
    # ord(A) = 65, ord(.) = 18
    a, b, c = ord(a)-64, ord(b)-64, ord(c)-64
    # 그래프 관계 연결시키기
    tree[a].append(b)
    tree[a].append(c)

preOrder(1)
print()
inOrder(1)
print()
postOrder(1)

 

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1991_%ED%8A%B8%EB%A6%AC%EC%88%9C%ED%9A%8C.py