[백준][BFS] 9934. 완전 이진 트리

9934. 완전 이진 트리

9934번: 완전 이진 트리

 

• 내 풀이
  
  • bfs
    • 중간 point로 앞 뒤 리스트를 나눠서 queue에 넣고 
    • 중간지점을 result에 순서대로 넣는다
    • => 앞 리스트, 뒷 리스트 하나하나씩 들어감
  • dfs 로 하게되면 앞리스트 전부 탐색 후 뒷 리스트를 탐색하기 때문에 순서대로 출력되지 못함

from collections import deque
  
def bfs(lst):
  queue.append(lst)

  while queue:
      x=queue.popleft()
      if len(x)<1: break
      point=len(x)//2
  
      result.append(x[point])
      queue.append(x[:point])
      queue.append(x[point+1:])
    

k=int(input()) #높이 k
lst=list(map(int,input().split()))

queue=deque()
point=len(lst)
result=[]
bfs(lst)

cnt=0
z=1
for r in result:
    print(r, end=" ")
    if z==1 or cnt==z:
        print()
        z*=2
        cnt=0
    cnt+=1

 

• 다른 사람 풀이
  • 레벨 크기만큼 리스트를 만들고 
  • 각 레벨 인덱스에 해당 레벨의 값들 append
  • dfs 파라미터로 레벨을 같이 전달

import sys
input = sys.stdin.readline
 
K = int(input())
lst = list(map(int, input().split()))
tree = [[] for _ in range(K)]
 
 
def makeTree(arr, x):
    mid = (len(arr)//2)
    tree[x].append(arr[mid])
    if len(arr) == 1:
        return
    makeTree(arr[:mid], x+1)
    makeTree(arr[mid+1:], x+1)
 
 
makeTree(lst, 0)
for i in range(K):
    print(*tree[i])