[자료구조] 17. 이진 트리 순회: 넓이 우선 탐색(Breadth First Search, BFS)

Posted Sep 16, 2023

By Jihyun,Ryu 6 min read

복습: 트리의 순회 (Traversal)

깊이 우선 순회 (Depth First Search, DFS): 트리의 루트에서 시작하여 가능한 깊이 들어가며 트리의 노드를 순회한다. 특정 노드에서 더 이상 깊이 들어갈 수 없게되면, 이전 노드로 돌아와 다음 노드를 방문하는 방식으로 순회가 진행된다.

넓이 우선 순회 (Breadth First Search, BFS): 트리의 루트에서 시작하여 같은 깊이에 있는 노드를 왼쪽에서 오른쪽으로 순회하고, 다음 깊이의 노드로 넘어가는 방식으로 순회가 진행된다.

이전 포스팅에서 언급되었듯이 이진 트리의 순회 로직은 깊이 우선 순회와 넓이 우선 순회로 구분되며, 이번 포스팅에서는 넓이 우선 순회에 관해서 정리할 것이다.

넓이 우선 탐색 (BFS)

넓이 우선 순회를 수행하기 위해서는 ❗반드시 지켜야할 다음과 같은 원칙이 있다.
1. 수준(Level)이 낮은 계층(즉, 루트 노드가 포함된 계층) 부터 방문한다
2. 동일 계층 내에서 노드의 방문은 이전 계층의 부모 노드의 방문 순서를 따라간다.
3. 동일 부모 노드를 가지는 자식 노드들은 왼쪽 자식부터 방문한다.

위의 원칙을 적용하여 다음의 트리를 넓이 우선 순회 방식으로 순회한 예제는 다음과 같다.
결과: A→B→C→D→E→F→G→H→I

넓이 우선 탐색의 과정

넓이 우선 순회는 깊이 우선 순회와 달리 재귀적인 구조로 표현하기 어렵다. 왜냐하면, 트리의 레벨을 고려하여 계층을 순차적으로 방문하는 방식이기 때문이다.

따라서, 넓이 우선 순회는 큐(Queue)를 이용하여 구현하는 것이 적합하다. 구현 핵심은 특정 노드를 방문했을 때 나중에 방문할 자식 노드를 큐에 순서대로 기록하는 것이다.

다음은 위에서 제시된 트리 구조를 큐 자료 구조를 이용하여 넓이 우선 순회를 순차적으로 설명한 예시이다. (*여기서 “방문”이라는 표현은 Enqueue후 Dequeue를 완료함을 의미한다.)
- Level 0 순회
  1. 루트 노드를 먼저 방문하고, 다음에 방문할 루트 노드의 자식 노드인 B와 C를 저장한다. → 결과: [A], 레벨 0 계층 순회 완료
- Level 1 순회
  1. 큐에 저장된 노드 B를 방문하고, 노드 B의 자식 노드인 D와 E를 순차적으로 큐에 저장한다. → 결과: [A, B]
  1. 동일 레벨의 노드 C를 방문하고, 노드C의 자식 노드인 F와 G를 순차적으로 큐에 저장한다. -> 결과:[A, B, C] , 레벨 1 계층 순회 완료
- Level 2 순회
  1. 큐에 저장된 노드 D를 방문하고, 노드 D의 자식 노드인 H를 큐에 저장한다. → 결과: [A, B, C, H]
  1. 동일 레벨의 노드 E를 방문한다. 노드 E는 자식 노드가 없으므로 프로세스를 종료한다. → 결과: [A, B, C, H, E]
  1. 동일 레벨의 노드 F를 방문한다. 노드 F의 자식 노드인 I를 큐에 저장한다. → 결과: [A, B, C, H, E, F]
  1. 동일 레벨의 노드 G를 방문한다. 노드 G는 자식 노드가 없으므로 프로세스를 종료한다. → 결과: [A, B, C, H, E, F, G]
- Level 3 순회
  1. 동일 레벨의 노드 I를 방문한다. 노드 I는 자식 노드가 없으므로 프로세스를 종료한다. → 결과: [A, B, C, H, E, F, I]
  1. 동일 레벨의 노드 H를 방문한다. 노드 H는 자식 노드가 없으며, 이후 큐 내에 더 이상 방문할 노드가 없으므로 넓이 우선 순회 프로세스를 완전히 종료한다.
    → 결과: [A, B, C, H, E, F, H]

넓이 우선 탐색 구현

위의 원칙에 따라 넓이 우선 순회(bft)를 구현하면 다음과 같다.

  
  from utils_practice.tree.node import Node
  from utils_practice.queue.queue import ArrayQueue
    
  class BinaryTree:
      def __init__(self, rootNode: Node):
          self.root = rootNode
    
      def bft(self):
    
          queue = ArrayQueue()
          traversal = []
    
          if self.root:
              queue.enqueue(self.root)
    
          while not queue.isEmpty():
              popNode = queue.dequeue()
              traversal.append(popNode.data)
    
              if popNode.left:
                  queue.enqueue(popNode.left)
    
              if popNode.right:
                  queue.enqueue(popNode.right)
    
          return traversal

References

Programmers, 어서와! 자료구조와 알고리즘은 처음이지?

Data, Data Structure

This post is licensed under CC BY 4.0 by the author.

복습: 트리의 순회 (Traversal)

넓이 우선 탐색 (BFS)

넓이 우선 탐색의 과정

넓이 우선 탐색 구현

References

Trending Tags