[WEEK03] DAY19

3주차 시작 !!

3주차 알고리즘 문제들의 주제는 그래프 탐색, DFS, BFS, 위상 정렬 이다.

그리고 그래프 탐색의 문제는 트리 문제로 시작되었다!
트리에 관한 정보를 빠르게 공부 ㅎㅅㅎ

* 트리

* DFS, BFS

그래프 탐색 기본

1991 트리순회

전위 순회 Preorder
중위 순회 Inorder
후위 순회 Postorder
레벨 순위 Levelorder

트리 구조를 코드로 어떻게 옮길 것인지에 대한 문제였다.

코드

import sys

def DFS1(node): #전위 preorder
    if node == '.': # 자식노드가 없으면 종료
        return
    else:
        print(node,end='')
        DFS1(tree[node][0]) # 왼쪽 자식 노드 탐색
        DFS1(tree[node][1]) # 오른쪽 자식 노드 탐색
        
def DFS2(node): #중위 inorder
    if node == '.':
        return
    else:
        DFS2(tree[node][0])
        print(node,end='')
        DFS2(tree[node][1])
        
def DFS3(node): #후위 postorder
    if node == '.':
        return
    else:
        DFS3(tree[node][0])
        DFS3(tree[node][1])
        print(node,end='')
                

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    tree = {}
    
    for _ in range(n):
        root, left, right = map(str, sys.stdin.readline().split())
        tree[root] = [left, right]
    
    DFS1('A')
    print()
    DFS2('A')
    print()
    DFS3('A')

.
.

5639 이진 검색 트리

맨 아래 왼쪽에 보면 어떻게 풀지는 다 구상을 했는데(정답이었음)
코드로는 어떻게 작성해야할지 감이 안와서 오래 걸렸었다

코드

(앞으로 내 코드에 주석이 아주 많아질 예정...!)

# # input file 기준 
# # 50 30 24 5 28 45 98 52 60 을
# # 5 28 24 45 30 60 52 98 50
import sys
sys.setrecursionlimit(100000) #재귀 반복횟수 늘림 (재귀 디폴트 1000개)
input = sys.stdin.readline
def getPostorder(nums):
    length = len(nums)
    # 입력받은 리스트의 길이가 1보다 작을 경우 리스트를 원본 그대로 반환
    if length <= 1:
        return nums
    # 루트 노드를 그대로 놔두려고 1부터 시작했나?
    for i in range(1, length):
        # 루트 노드(nums[0])보다 받은 값이 큰 경우 오른쪽 서브트리로 이동
        if nums[i] > nums[0]:
            # 왼쪽 서브트리 + 오른쪽 서브트리 + 루트 
            # 큰수 비교하는 동시에 서브트리를 후위 순회로 바꿔줌
            return getPostorder(nums[1:i]) + getPostorder(nums[i:]) + [nums[0]]
    # 맨 마지막 작업. 후위 순회는 루트 노드가 맨 마지막에 오니까 순서바꾸기
    return getPostorder(nums[1:]) + [nums[0]] #최종 후위 순회~
if __name__ == '__main__':
    nums = []
    while True:
        try:
            nums.append(int(input()))
        except:
            break
    # 재귀 최종 리턴 받은 값들 후위 순회로 받음
    nums = getPostorder(nums)
    for n in nums:
        print(n)

결국 구글링하며 여러 코드들을 읽어봄 ㅎㅎ

오늘은 문제를 풀기 전에 베이스를 먼저 공부하는 데에 하루 시간을 많이 들인 것 같다.
내일은 문제 쭉 봐야지

오늘의 다짐

주석 다는 습관을 들이자!!! ♥