너비 우선 탐색(BFS)

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

너비 우선 탐색 - 이진 트리

  • 루트에서 시작
  • 각 레벨의 모든 노드를 방문

이진 탐색 트리에서의 너비 우선 탐색 애니메이션.

Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):

    if self.root:

      visited_nodes = []

      bfs_queue = queue.SimpleQueue()

이진 탐색 트리의 그래픽 표현.

  • visited_nodes:
  • bfs_queue:
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)

      while not bfs_queue.empty():

이진 탐색 트리의 그래픽 표현.

  • visited_nodes:
  • bfs_queue: 65
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()

이진 탐색 트리의 그래픽 표현.

  • visited_nodes:
  • bfs_queue:
  • current_node: 65
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)

        if current_node.left:

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65
  • bfs_queue:
  • current_node: 65
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):

    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65
  • bfs_queue: 20
  • current_node: 65
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65
  • bfs_queue: 20, 70
  • current_node: 65
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65
  • bfs_queue: 70
  • current_node: 20
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20
  • bfs_queue: 70
  • current_node: 20
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20
  • bfs_queue: 70, 10
  • current_node: 20
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20
  • bfs_queue: 70, 10, 22
  • current_node: 20
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20
  • bfs_queue: 10, 22
  • current_node: 70
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70
  • bfs_queue: 10, 22
  • current_node: 70
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70
  • bfs_queue: 10, 22, 68
  • current_node: 70
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70
  • bfs_queue: 10, 22, 68, 75
  • current_node: 70
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70, 10
  • bfs_queue: 22, 68, 75
  • current_node: 10
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70, 10
  • bfs_queue: 68, 75
  • current_node: 22
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70, 10, 22
  • bfs_queue: 68, 75
  • current_node: 22
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70, 10, 22, 68
  • bfs_queue: 75
  • current_node: 68
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70, 10, 22, 68
  • bfs_queue:
  • current_node: 75
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70, 10, 22, 68, 75
  • bfs_queue:
  • current_node: 75
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 이진 트리

  def bfs(self):
    if self.root:
      visited_nodes = []
      bfs_queue = queue.SimpleQueue()
      bfs_queue.put(self.root)
      while not bfs_queue.empty():
        current_node = bfs_queue.get()
        visited_nodes.append(current_node.data)
        if current_node.left:
          bfs_queue.put(current_node.left)
        if current_node.right:
          bfs_queue.put(current_node.right)
    return visited_nodes
  • 복잡도: $O(n)$

이진 탐색 트리의 그래픽 표현.

  • visited_nodes: 65, 20, 70, 10, 22, 68, 75
  • bfs_queue:
  • current_node: 75
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 그래프

  • 그래프에는 순환이 있을 수 있음
    • 정점을 이미 방문했는지 확인 필요
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 그래프

def bfs(graph, initial_vertex):

  visited_vertices = []

  bfs_queue = queue.SimpleQueue()

  bfs_queue.put(initial_vertex)

  visited_vertices.append(initial_vertex)

  while not bfs_queue.empty():

    current_vertex = bfs_queue.get()

    for adjacent_vertex in graph[current_vertex]:

      if adjacent_vertex not in visited_vertices:

        visited_vertices.append(adjacent_vertex)

        bfs_queue.put(adjacent_vertex)

  return visited_vertices
  • 복잡도: $O(V+E)$
    • $V$ -> 정점 수
    • $E$ -> 간선 수
Python으로 배우는 자료구조와 알고리즘

너비 우선 탐색 - 그래프

그래프에서의 너비 우선 탐색 애니메이션.

Python으로 배우는 자료구조와 알고리즘

BFS vs DFS

BFS

  • 목표가 시작 정점과 가깝습니다
  • 활용:
    • 웹 크롤링
    • 무가중치 그래프 최단 경로
    • GPS로 연결된 위치 찾기
    • 복잡한 알고리즘의 일부로 사용

DFS

  • 목표가 시작 정점에서 멉니다
  • 활용:
    • 해가 하나인 퍼즐 풀이(예: 미로)
    • 그래프 사이클 탐지
    • 가중치 그래프 최단 경로
    • 복잡한 알고리즘의 일부로 사용
Python으로 배우는 자료구조와 알고리즘

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘

Preparing Video For Download...