BFS (Breadth-First Search)

fixy·2025년 8월 21일
탐색 방법론

그래프나 트리와 같은 자료 구조에서 한 노드에서 시작해 인접한 노드들을 먼저 모두 탐색하는 알고리즘

  • 가까운 노드부터 '수평적으로' 탐색하는 것이 특징

⭐ BFS의 특징

✅ 1. 너비 우선 탐색

  • 시작 노드로부터 가까운 노드를 먼저 탐색합니다. 특정 깊이에 있는 모든 노드를 먼저 방문한 후, 다음 깊이로 넘어감

✅ 2. 큐(Queue) 사용

  • BFS는 선입선출(FIFO) 구조인 큐(Queue)를 사용
  • 큐에 들어간 순서대로 노드를 탐색하므로, 가까운 노드부터 처리할 수 있음

✅ 3. 재귀(Recursion) 사용하지 않음

  • 일반적으로 DFS(깊이 우선 탐색)와 달리, BFS는 재귀 호출을 사용하지 않고 반복문(while, for)을 사용하여 구현

✅ 4. 최단 경로 보장

  • 모든 간선 가중치가 동일할 때, 시작 노드에서 목표 노드까지의 최단 경로를 항상 보장
  • 시작 노드로부터 거리가 1인 모든 노드를 탐색하고, 그다음 거리가 2인 모든 노드를 탐색하는 방식으로 진행되기 때문

DFS는 스택 또는 재귀 사용하고, 최단 경로 보장 불가함

📌 BFS의 단계

✅ 1. 시작점

  • 탐색을 시작할 노드를 선택하고 큐에 넣은 뒤, 방문 처리

✅ 2. 노드 탐색

  • 큐가 빌 때까지 다음을 반복

✅ 3. 큐에서 꺼내기

  • 큐의 맨 앞에서 노드를 하나 꺼내기

✅ 4. 인접 노드 확인

  • 꺼낸 노드와 연결된 모든 인접 노드를 확인

✅ 5. 방문 처리 및 큐에 추가

  • 아직 방문하지 않은 인접 노드가 있다면, 방문 처리하고 큐에 추가

❗ BFS의 구현

✅ 1. 큐(Queue) 자료 구조를 이용한 구현

  • 큐는 먼저 들어간 데이터가 먼저 나오는 FIFO(First-In, First-Out) 방식이므로, 시작 노드로부터 가까운 노드를 먼저 탐색하는 BFS의 원리와 정확히 일치

  • 파이썬의 collections.deque는 양방향 큐로, 노드를 넣고 빼는 작업이 매우 효율적이어서 BFS 구현에 자주 사용

  • 구현 과정

      1. 큐와 방문 집합 초기화:
        탐색할 노드를 담을 큐와 이미 방문한 노드를 기록할 방문(visited) 집합을 만듦. 시작 노드를 큐에 넣고 방문 집합에 추가함.
      1. 반복문:
        큐가 비어 있지 않은 동안 반복
      1. 노드 추출:
        큐의 맨 앞에서 노드를 하나 꺼냄
      1. 인접 노드 탐색:
        현재 노드와 연결된 모든 인접 노드를 확인
      1. 새 노드 추가:
        인접 노드 중 아직 방문하지 않은 노드가 있다면, 해당 노드를 방문 집합에 추가하고 큐의 맨 뒤에 넣음

✅ 2. 재귀(Recursion)를 이용한 구현

  • 이론적으로 큐를 전역 변수로 관리하는 방식으로 재귀적인 BFS를 구현할 수 있음
  • 매우 비효율적이고 비직관적이기 때문에 실용적인 예시에서는 거의 찾아보기 어려움

일반적인 BFS 구현 방식은 오직 큐를 이용한 반복문 방식임. 다양한 구현 방법을 찾는 경우, 큐를 배열이나 리스트로 구현하는 방법 등을 생각해볼 수 있지만, 근본적인 탐색 원리는 동일함.

⚠️ BFS의 장단점

✅ 장점

  • 최단 경로 탐색:

    • 가중치가 없는 그래프에서 최단 거리를 보장
    • BFS는 시작 노드에서부터 한 레벨씩 모든 노드를 탐색하므로, 목표 노드에 처음 도달했을 때의 경로가 가장 짧은 경로가 됨

  • 탐색의 안정성:

    • 탐색이 단계별로 확장되기 때문에 특정 깊이 내에서 답을 찾아야 하는 문제에 유리
    • ex) 특정 노드와 3단계 이내로 연결된 모든 노드를 찾고 싶을 때, BFS는 3단계 탐색 후 바로 멈출 수 있어 효율적임

❌ 단점

  • 메모리 사용량:
    • 탐색해야 할 그래프의 크기가 크고, 특히 가지가 넓게 퍼지는 경우(가지치기 계수가 큰 경우), 큐에 매우 많은 노드를 저장해야 하므로 메모리를 많이 소비
    • DFS가 주로 스택을 사용하고 한 경로를 깊게 탐색하는 것과 대조적
  • 비효율적인 탐색:
    • 만약 목표 노드가 시작 노드로부터 매우 깊은 곳에 위치하거나, 그래프의 한쪽 끝에 있다면, BFS는 불필요하게 넓은 영역을 모두 탐색해야 할 수 있음
    • 이 경우, 한 방향으로 깊게 탐색하는 DFS가 더 효율적일 수 있음
  • 가중치 그래프 문제:
    • 간선에 가중치(비용)가 있는 그래프에서는 최단 경로를 보장하지 못함
    • ex) 짧은 거리를 여러 번 거치는 경로가 긴 거리 한 번에 도달하는 경로보다 짧을 수 있는데, BFS는 단순히 단계(레벨)만 고려하기 때문
    • 가중치 그래프의 최단 경로는 다익스트라(Dijkstra)나 벨만-포드(Bellman-Ford) 알고리즘을 사용

📝 예제

BFS를 사용했을 때 탐색 순서는 어떻게 되는가?

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

다음과 같은 그래프가 있다.
그래프는 노드와 노드 사이의 연결로 이루어져 있다.
너비 우선 탐색(BFS)을 이용해 모든 노드를 방문하는 순서를 구하라.

조건

  • 시작 노드는 A
  • 같은 레벨(같은 거리에 있는 노드)부터 방문
  • 각 노드는 한 번만 방문
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}
  1. 시작 노드를 큐에 넣는다.
  2. 큐에서 노드를 하나 꺼낸다.
  3. 그 노드의 인접한 노드 중 방문하지 않은 노드를 모두 큐에 넣는다.
  4. 큐가 빌 때까지 반복

--> 같은 레벨(거리)에 있는 노드들을 먼저 방문하는 방식

from collections import deque  # BFS에서 사용할 큐 자료구조 import

def bfs(graph, start):
    visited = set()        # 이미 방문한 노드를 기록하는 집합
    queue = deque([start]) # BFS는 큐(Queue) 사용, 시작 노드를 넣음
    order = []             # 방문 순서를 저장할 리스트

    while queue:           # 큐가 빌 때까지 반복
        node = queue.popleft()  # 큐에서 가장 앞에 있는 노드를 꺼냄 (FIFO)
        if node not in visited: # 아직 방문하지 않은 노드이면
            visited.add(node)   # 방문 표시
            order.append(node)  # 방문 순서를 리스트에 저장

            # 현재 노드의 인접 노드들을 확인
            # 작은 번호 순서대로 큐에 추가 (옵션: 테스트에서 작은 번호 먼저 방문)
            for neighbor in sorted(graph[node]):
                if neighbor not in visited:  # 이미 방문한 노드는 큐에 넣지 않음
                    queue.append(neighbor)  # 다음에 방문할 노드로 큐에 추가

    return order  # BFS 탐색 순서 반환


# ---------------------
# 입력 처리
# ---------------------
n, m = map(int, input().split())  # 정점 개수(n)와 간선 개수(m) 입력
graph = {i: [] for i in range(1, n+1)}  # 1~n까지의 정점을 키로 하는 빈 리스트 생성

for _ in range(m):
    u, v = map(int, input().split())  # 간선 연결 정보 입력
    graph[u].append(v)                # u->v 연결
    graph[v].append(u)                # v->u 연결 (무방향 그래프)

start = int(input())  # 시작 정점 입력

# BFS 실행
result = bfs(graph, start)
print(' '.join(map(str, result)))  # 방문 순서 출력

적용 결과

  1. 시작: 큐에 ['A']를 넣는다. visited는 {'A'}가 된다.
  2. 노드 A: 큐에서 A를 꺼낸다. 방문 순서에 A를 추가한다. A의 인접 노드인 B, C를 큐에 넣는다. (알파벳 순으로 정렬되어 있으므로 B가 먼저 들어간다.) 큐는 ['B', 'C']가 된다.
  3. 노드 B: 큐에서 B를 꺼낸다. 방문 순서에 B를 추가한다. B의 인접 노드인 D를 큐에 넣습니다. 큐는 ['C', 'D']가 된다.

...

  1. 노드 F: 큐에서 F를 꺼낸다. 이미 visited에 있으므로 아무 작업도 하지 않고 건너뛴다. 큐는 비게 된다.
  2. 종료: 큐가 비었으므로 반복이 종료된다.

--> 최종 방문 순서는 A -> B -> C -> D -> E -> F

🔎 BFS의 주요 활용 예시

✅ 1. 최단 경로 찾기

BFS의 가장 대표적인 활용 예시로, 가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 찾는 데 사용됨. 이는 BFS가 시작 노드로부터 같은 거리에 있는 모든 노드를 먼저 탐색하는 '너비 우선' 방식 때문.

  • 동작 방식
      1. 시작 노드: 시작 노드로부터 한 단계씩 거리를 넓혀가며 탐색을 진행. 큐에 현재 레벨의 모든 노드를 넣고, 큐가 빌 때까지 노드를 꺼내고 인접 노드를 큐에 추가하는 과정을 반복.
      1. 거리 기록: 각 노드를 방문할 때, 시작 노드로부터의 거리를 기록하면 최단 거리를 쉽게 계산할 수 있음. 예를 들어, 시작 노드의 거리를 0으로 설정하고, 인접 노드의 거리는 현재 노드의 거리 + 1로 설정합니다.
profile
fixy
코딩 공부
이전 포스트

DFS (Depth-First Search)

다음 포스트

#24511 queue & stack

0개의 댓글