BFS

Hyunwoo·2025년 8월 23일

BFS 그래프 알고리즘 자료구조 트리

알고리즘

목록 보기

2/6

BFS(너비 우선 탐색) 완전 정리

BFS(Breadth-First Search)는 그래프 탐색 알고리즘 중 하나로, 이름 그대로 너비 우선으로 탐색.

1. BFS란?

정의: 시작 정점에서 인접한 노드들을 먼저 방문하고, 그 다음 레벨로 넘어가는 순서대로 탐색하는 알고리즘
자료구조: FIFO 구조인 큐(Queue) 사용
특징:
1. 레벨별 탐색 → 시작점에서의 최단 경로 계산 가능
2. 방문 순서는 시작점으로부터 거리 순
3. 재귀보다 스택 오버플로우 위험이 적음 (DFS 재귀 깊이 문제 X)

2. BFS 동작 원리

그래프 (G = (V, E))가 주어질 때, BFS는 다음과 같이 동작.

시작점 (s) 방문, dist[s] = 0
큐 (Q)에 (s) 삽입
큐가 빌 때까지 반복:
- (u = Q.dequeue())
- 모든 (v ∈ Adj[u])에 대해:
  - 방문하지 않았다면:
    - dist[v] = dist[u] + 1
    - parent[v] = u
    - Q.enqueue(v)

즉, BFS는 그래프를 "계층적 탐색 트리(Level Tree)"로 변환하는 과정

3. BFS의 시간·공간 복잡도

시간:
- 인접 리스트 사용 시: O(V + E)
- 인접 행렬 사용 시: O(V^2) (큰 그래프에서는 비효율적)
공간:
- 큐 + 방문/거리 배열: O(V)
- 경로 복원 배열 추가 시: O(V)

4. BFS 구현 시 주의점

4-1. 방문 체크 시점

# 큐에 넣을 때 체크 (권장)
for v in adj[u]:
    if not visited[v]:
        visited[v] = True
        q.append(v)

중요: 큐에서 꺼낼 때 체크하면 중복 삽입 발생 → 비효율적

4-2. 최단 거리 계산

BFS는 가중치가 동일한 그래프에서만 최단 거리 보장
다른 가중치라면 다익스트라 혹은 0-1 BFS 사용

4-3. 멀티 소스 BFS

여러 시작점에서 동시에 BFS 수행 가능
큐에 모든 시작점 넣고 dist[start]=0 초기화
전파 문제(토마토, 불 확산)에서 자주 사용

5. BFS를 이용한 경로 복원

def reconstruct_path(parent, target):
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    return path[::-1]

BFS 탐색 중 parent[v] = u 기록
목표 지점에서 부모를 따라가면서 최단 경로 복원 가능
DFS는 최단 경로를 보장하지 않음 → BFS 사용 필수

6. 격자(2D) BFS 예제

미로, 섬 찾기 등 격자 그래프 문제
좌표 (y, x)를 노드로 처리, 상하좌우 이동

from collections import deque

def bfs_grid(board, start):
    n, m = len(board), len(board[0])
    dist = [[-1]*m for _ in range(n)]
    q = deque([start])
    dist[start[0]][start[1]] = 0
    dirs = [(0,1),(1,0),(0,-1),(-1,0)] # 4방향

    while q:
        y, x = q.popleft()
        for dy, dx in dirs:
            ny, nx = y+dy, x+dx
            if 0 <= ny < n and 0 <= nx < m and board[ny][nx]==0 and dist[ny][nx]==-1:
                dist[ny][nx] = dist[y][x] + 1
                q.append((ny, nx))
    return dist