7/9 코테 일지 (BFS 응용)

1. BFS 응용 

11725 트리의 부모 찾기 

처음에는 트리의 특성을 사용하지 않고 단순히 논리적으로 queue를 사용하여 풀었다. 

import sys 
from collections import deque

n = int(sys.stdin.readline().rstrip())
ans = [0 for _ in range(n)]
ans[0] = 1 
queue = deque()

for _ in range(n-1):
  input = list(map(int,sys.stdin.readline().rstrip().split(' ')))
  queue.append(input)

while queue:
  input = queue.popleft()
  if ans[input[0]-1] != 0 :
    ans[input[1]-1] = input[0]
  elif ans[input[1]-1] != 0 :
    ans[input[0]-1] = input[1]
  else :
    queue.append(input)

for i in ans[1:]:
  print(i)

53%에서 시간초과가 떠서 질문게시판에 질문을 하여서 답변을 받았는데 당연히 시간초과가 뜨는게 당연한 답안이었다. (오히려 시간초과가 떠서 다행이다.)

다음과 같이 루트의 역순으로 정보가 주어질 경우 while문은 N(N-1)/2이 실행된다. 굉장히 비효율적이다.

9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
2 1

 

따라서 이런 경우를 회피하기 위해 트리의 특성을 사용해야 한다. Breadth first search를 사용하면 루트 노드의 자식부터 하나씩 부모노드 정보를 업데이트 시켜가며 답을 구할 수 있다. 이 글을 보면 정확한 알고리즘이 이해 될 것이다. 해당 블로그글의 작성자는 dictionary를 사용하였지만 나는 리스트를 사용하였는데 큰 차이가 없을 것이다. 

import sys 
from collections import deque

n = int(sys.stdin.readline().rstrip())
temp = [[] for _ in range(n)]
queue = deque()
for _ in range(n-1):
  input = list(map(int,sys.stdin.readline().rstrip().split(' ')))
  temp[input[0]-1].append(input[1])
  temp[input[1]-1].append(input[0])

queue.append(1)
ans = [0] * (n)
ans[0] = 1 
cnt= 0 
while queue:
  cnt += 1
  curr = queue.popleft()
  for i in temp[curr-1]:
    if ans[i-1] == 0:
      ans[i-1] = curr
      queue.append(i)

for i in ans[1:]:
  print(i)

 

 

2. 

https://neetcode.io/problems/binary-tree-right-side-view

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        queue = deque()
        ans = []
        if root :
            queue.append(root)
        while queue:
            for _ in range(len(queue)):
                curr = queue.popleft()
                if curr.left :
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            ans.append(curr.val)
        return ans

 

3.

https://neetcode.io/problems/level-order-traversal-of-binary-tree

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        queue = deque()
        if root :
            queue.append(root)

        level=0
        ans = []
        
        while (queue):
            ans.append([])
            for _ in range(len(queue)):
                curr= queue.popleft()
                ans[level].append(curr.val)
                if curr.left :
                    queue.append(curr.left)
                if curr.right :
                    queue.append(curr.right)
            level += 1 
        return ans

 

4.

9934 완전 이진 트리

import sys
n = int(sys.stdin.readline().rstrip())
list = list(map(int,sys.stdin.readline().rstrip().split(' ')))

level=0
ans= [[] for _ in range(n)]
def answer(array,level) :
  if not array:
    return
  mid = int(len(array)/2)
  ans[level].append(array[mid])
  level += 1
  answer(array[0:mid],level)
  answer(array[mid+1:],level)

answer(list,0)
for i in ans :
  print(*i)