파이썬 알고리즘 : 트리 순회, 이진 검색 트리, 최소 스패닝 트리
2023년 8월 3일 알고리즘 문제풀이 백준 1991 문제 링크 1차 시도 나의 생각 왼쪽 자식이 존재하면 재귀를 통해 들어가고, 없을 때 오른쪽 자식도 확인하는 과정을 거쳤다. 정답을 위한 배열에 왼쪽 자식과 부모, 오른쪽 자식을 어느 타이밍에 추가해야할 지 헷갈렸고 이로 인해 코드를 완성하지 못했다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import sys arr = [] n = int(sys.stdin.readline()) for _ in range(n): p, l, r = sys.stdin.readline().rstrip().split() arr.append([p, l, r]) front = ['A'] mid = [] back = [] def search_front(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': ans.append(x[1]) search_front(x, arr, ans) if x[2] != '.': ans.append(x[2]) search_front(x, arr, ans) def search_mid(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_mid(x, arr, ans) else: ans.append(x[0]) if x[2] != '.': search_mid(x, arr, ans) break def search_back(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_back(x, arr, ans) else: ans.append(node) if x[2] != '.': search_back(x, arr, ans) ans.append(x) ans.append(node[0]) search_front(arr[0], arr, front) search_mid(arr[0], arr, mid) search_back(arr[0], arr, back) print(front) print(mid) print(back) 2차 시도 나의 생각 정답을 위한 배열에는 항상 부모만 넣는다는 기준을 세웠다. 또 왼쪽자식과 오른쪽 자식의 탐색을 if-else 조건문을 사용하였는데 별개로 하였다. 즉 왼쪽 자식을 먼저 탐색해 존재하면 재귀를 통해 최대한 깊숙히 들어간 후 더이상 왼쪽자식이 존재하지 않을 때 그 때의 부모노드를 배열에 추가하면 전체 트리에서 가장 왼쪽에 있는 노드를 배열에 추가한 것으로 구현된다는 것을 깨달았다. 순회의 방식에 따라 왼쪽 자식 탐색, 부모노드 삽입, 오른쪽 자식 탐색의 순서만 변경해주었다. ...