dongzzirit 님의 블로그

1. 개념

BFS는 그래프나 트리에서 가장 가까운 노드부터 차례로 탐색해 나가는 알고리즘이다.
주로 큐(Queue) 자료구조를 사용하여 구현하며, 최단 거리 탐색이 필요한 문제에 적합하다.

2. 동작 방식

1. 시작 노드를 큐에 삽입하고 방문 표시
2. 큐에서 노드를 하나 꺼냄
3. 꺼낸 노드의 인접한 노드(또는 자식 노드)를 모두 확인
4. 아직 방문하지 않은 노드를 큐에 삽입
5. 큐가 빌 때까지 2~4번 반복

3. 트리 예시로 이해하기

트리 구조 예시

       A
     /   \
    B     C
   / \   / \
  D   E F   G

BFS 탐색 순서

• 시작 노드: A
• 방문 순서: A → B → C → D → E → F → G

큐와 방문 순서 변화

단계 큐 상태 방문한 노드

4. 파이썬 코드 예시 (트리 기준)

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def bfs(root):
    if root is None:
        return []

    visited = []
    q = deque([root])

    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)

    return visited

nodeD = Node("D")
nodeE = Node("E")
nodeF = Node("F")
nodeG = Node("G")
nodeB = Node("B", left=nodeD, right=nodeE)
nodeC = Node("C", left=nodeF, right=nodeG)
nodeA = Node("A", left=nodeB, right=nodeC)

5. 특징 요약

항목 설명