[알고리즘] 백준 | 1991 트리 순회, 14244 트리만들기

트리 순회

답: 

# 전위 순회
def preorder(root):
    if root != ".": # {'A': ['B', 'C']}
        print(root, end="")
        preorder(tree[root][0])
        preorder(tree[root][1])

# 중위 순회
def inorder(root):
    if root != ".":
        inorder(tree[root][0])
        print(root, end="")
        inorder(tree[root][1])

# 후위 순회
def postorder(root):
    if root != ".":
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root, end="")

N = int(input())
tree = {}
for _ in range(N):
    root, l, r = input().split()
    tree[root] = [l, r]

print(tree)
# {'A': ['B', 'C'], 'B': ['D', '.'], 'C': ['E', 'F'],
#  'E': ['.', '.'], 'F': ['.', 'G'], 'D': ['.', '.'], 'G': ['.', '.']}

preorder("A")
print()
inorder("A")
print()
postorder("A")

 

 

문제 분석 및 해석

1번째 줄에는 주어질 input 줄 수, 나머지 줄에  . 혹은 알파벳으로 이루어진 문자열이 주어질때,

트리의 전위, 중위, 후위순회를 각각의 줄에 차례로 출력하시오

 

 

>> 풀이생각

 

트리의 기본 알고리즘에 대해 문서를 읽고 공부하였다.

 

기본 식은 재귀로 이루어지며, left, right를 각각 재귀로 불러오면 된다는 것,

print 문을 어디에 적어주느냐에 따라 전위, 중위, 후위 순회 결과를 출력할 수 있음을 알게 되었다.

 

# 전위순회 기본 식
def preorder(root):
    if root != 0:
        yield root.value # 전위
        preorder(root.left)
        # yield root.value # 중위
        preorder(root.right)
        # yield root.value # 후위

 

 

리뷰.

어떤 식으로 풀이하는지에 대해 익숙해지기위해

식을 보고 풀이를 해석하며 클론코딩으로 공부하였다.

 

전위, 중위, 후위 순회의 출력 상태를 보고 파악하는 것도 연습해야할 듯.

 

---

 

트리 만들기

답: 

완전히 풀어내지 못해 다른분 코드 참고...

n, m = map(int, input().split())
 
# 리프의 개수
leaf = 0
if m == 2:
    leaf = 1  # 중심 노드를 리프로 포함
 
last_leaf = 0
for i in range(1, n):
    if m > leaf:
        print(0, i)
        leaf += 1
    else:
        print(last_leaf, i)
    last_leaf = i

 

 

문제 분석 및 해석

전체 노드 개수 n과 리프노드 개수 m이 첫 줄에 주어질 때,

트리의 간선을 출력하시오

 

입력

4 2

 

출력

0 1

1 2

2 3

 

>> 풀이생각

 

 

 

과정.

 

입력값 n, m 받기

n, m = map(int, input().split())

 

일단 root값을 0으로 잡아주고 재 저장하는 식으로 풀이하고자 했다.

root = 0
for i in range(1, n - 1): # 0 1 / 1 2
    print(root, i)
    root = i

# m - 1 개가 진짜 리프노드 값, n - 1 과 이어져야함
for i in range(root, root + (n-m)):
    print(root, i)

 

 

문제는 4 2, 3 2 케이스와 4 3, 5 3 케이스...

그러니까 노드가 2개인 케이스와 다른 케이스 간에 제대로 출력되지 않는 문제가 생겼다.

 

재저장되는 root값이 1개 더 큰 수가 나오거나 미출력되거나 하는 문제였고,

해결하지 못해 다른 사람의 풀이를 보며 해석하며 공부하였다.

 

 

 

리뷰

 

1. '트리의 간선'이라는 용어 자체가 생소해서 문제를 이해하는데에 도움을 받아야 했다

이후 예제를 그림을 그려가며 이해했음

 

 

2. 생소한 자료구조를 한 번에 풀이까지 적용할 수 있으리라 생각은 안했지만

그렇게까지 어려운 문제는 아니었던 것 같아서 많이 아쉽다

새로운 자료구조를 시작하며 구현에서의 부족한 점이 많이 느껴진다.

이번 주 동안 최대힙 최소힙 트리 문제를 계속 풀어보며 익숙해지자

 

 

 

문제해석과 풀이 방법은 아래 블로그를 참고...

https://tarra.tistory.com/entry/%EB%B0%B1%EC%A4%80-14244%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0-python