BFS 최단거리 탐색의 원리와 활용

BFS란?

Breadth-First Search (BFS)는 그래프나 트리에서
현재 노드의 이웃 노드를 먼저 방문하고,
그 다음 단계로 넘어가는 너비 우선 탐색 알고리즘입니다.

 

즉, 깊이보다 가까운 노드부터 차례대로 탐색하는 방식입니다.

---

BFS의 핵심 특징

특징	설명
우선순위	가까운(레벨 낮은) 노드부터 탐색
자료구조	Queue(큐)
구현 방식	반복문 기반
대표 사용처	최단거리 탐색, 그래프 레벨 구분, 게임 맵 탐색 등

---

BFS 기본 구현 (Python)

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for neighbor in graph[v]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

---

예제 그래프와 실행

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}
bfs(graph, 1)

# 1 2 3 4 5

가까운 노드부터 한 층씩 탐색함

---

BFS의 대표 활용 – 최단거리 탐색

BFS는 간선의 가중치가 모두 동일한 그래프에서
시작점에서 각 노드까지의 최단거리를 구할 수 있습니다.,

 

예시: 미로 탐색 (2차원 배열)

from collections import deque

def shortest_path(maze, start):
    n, m = len(maze), len(maze[0])
    visited = [[False]*m for _ in range(n)]
    dist = [[0]*m for _ in range(n)]

    queue = deque([start])
    visited[start[0]][start[1]] = True

    directions = [(-1,0), (1,0), (0,-1), (0,1)]

    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x+dx, y+dy
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))
    
    return dist

---

DFS와의 차이점

항목	BFS	DFS
자료구조	Queue	Stack / Recursion
탐색 순서	가까운 노드부터	깊은 노드부터
최단거리	가능	보장 안 됨
경로 탐색	제한된 경우 적합	전체 경로 탐색에 적합
사용 예	미로, 게임 맵, 그래프 거리	조합, 퍼즐, 경로 전수조사

---

시간복잡도

• 시간복잡도: O(V + E)
• 공간복잡도: O(V) (큐, visited, 거리 배열 등)

---

상황별정리

상황	BFS가 적합한 이유
최단 거리 문제	방문 순서가 거리 순서이기 때문에
게임 맵 이동	레벨 단위 탐색이 필요
사회적 거리 분석	연결된 노드를 사아의 거리 측정