anonymous.rs

알고리즘: 너비 우선 탐색 (BFS, Breadth-First Search)

7 min read

너비 우선 탐색 (BFS, Breadth-First Search) 완벽 가이드

그래프와 트리 구조를 탐색하는 가장 대표적인 알고리즘 두 가지 중 하나인 **너비 우선 탐색(BFS)**에 대해 알아보겠습니다. 코딩 테스트에서 ‘최단 경로’나 ‘최소 횟수’를 구하라는 문제가 나오면 가장 먼저 떠올려야 하는 핵심 알고리즘입니다.

1. BFS란?

BFS는 시작 정점(Node)에서 출발하여 가장 가까운(인접한) 정점들을 먼저 모두 방문하고, 그 다음으로 가까운 정점들을 방문하는 방식으로 그래프를 넓게 탐색하는 알고리즘입니다.

마치 연못에 돌을 던졌을 때 물결이 동심원을 그리며 퍼져나가는 모습이나, 방사형으로 주변을 샅샅이 수색하는 방식을 떠올리면 이해하기 쉽습니다.

2. 동작 과정과 큐(Queue)

BFS 알고리즘은 큐(Queue) 자료구조를 사용하여 구현합니다. 먼저 들어온 데이터가 먼저 나가는 FIFO(First-In, First-Out) 특성이 ‘먼저 발견한 가까운 노드를 먼저 탐색’하는 BFS의 성질과 정확히 일치하기 때문입니다.

  1. 시작 정점 방문: 시작 정점을 큐에 삽입하고, ‘방문했음(Visited)‘을 표시합니다.
  2. 큐에서 추출: 큐에서 정점을 하나 꺼냅니다.
  3. 인접 정점 탐색: 꺼낸 정점과 연결된 모든 인접 정점들을 확인합니다.
  4. 큐에 삽입: 인접 정점들 중 ‘아직 방문하지 않은 정점’이 있다면, 그 정점들을 모두 큐에 넣고 방문 처리를 합니다.
  5. 반복: 큐가 완전히 빌 때까지 2~4번 과정을 반복합니다.

3. 파이썬(Python) 구현 예시

파이썬에서는 효율적인 큐 연산을 위해 collections.deque를 사용하는 것이 표준입니다.

from collections import deque
 
def bfs(graph, start_node):
    # 방문 여부를 기록할 리스트 (또는 Set)
    visited = []
    
    # 큐 초기화 및 시작 노드 삽입
    queue = deque([start_node])
    
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 노드를 하나 꺼냄
        current = queue.popleft()
        
        # 아직 방문하지 않은 노드라면 방문 처리
        if current not 제 in visited:
            visited.append(current)
            print(f"방문: {current}")
            
            # 현재 노드와 연결된 인접 노드들 중 방문하지 않은 노드를 큐에 추가
            for neighbor in graph[current]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    
    return visited
 
# 그래프 인접 리스트 예시
# 1번 노드와 2, 3, 4번이 연결되어 있고...
graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}
 
print("BFS 탐색 순서:")
bfs_result = bfs(graph, 1)
# 예상 출력: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
# (같은 깊이인 2, 3, 4를 먼저 모두 방문한 뒤 다음 깊이로 넘어감)

(참고: 위 코드는 이해를 돕기 위해 직관적으로 작성되었으며, 실제 알고리즘 문제에서는 visited = [False] * N 형태의 불리언 배열을 사용하여 방문 체크를 로 최적화하는 것이 일반적입니다.)

4. 시간 복잡도 및 공간 복잡도

정점(Vertex/Node)의 수를 , 간선(Edge)의 수를 라고 할 때:

  • 시간 복잡도:
    • 인접 리스트로 구현 시: 모든 정점을 한 번씩 큐에 넣고 빼며(), 각 정점에서 연결된 간선을 모두 확인하므로(), 총 의 시간이 걸립니다.
    • (만약 인접 행렬로 구현했다면 이 됩니다.)
  • 공간 복잡도:
    • 최악의 경우 큐(Queue)에 모든 정점이 들어갈 수 있으며, 방문 기록(Visited)을 저장하는 배열도 의 공간을 차지합니다.

5. BFS의 핵심 활용 사례

인터뷰에서 다음과 같은 상황이 주어지면 무조건 BFS를 먼저 고려해야 합니다.

  1. 가중치 없는 그래프의 최단 경로: 시작점에서 목표점까지 가는 여러 경로 중 **가장 적은 간선을 거치는 경로(최단 거리, 최소 이동 횟수)**를 찾을 때 절대적입니다. (미로 찾기, 나이트의 이동 등)
  2. 연결된 구성 요소 찾기 (Connected Components): 섬의 개수 구하기, 바이러스 전파 범위 구하기 등 한 그룹으로 연결된 모든 영역을 칠하는(Flood Fill) 문제.
  3. 동심원 탐색: 특정 노드로부터 거리가 이하인 모든 노드를 찾을 때.

요약

BFS(너비 우선 탐색)는 큐(Queue)를 활용하여 가까운 곳부터 꼼꼼하게 넓혀가며 탐색하는 알고리즘입니다. 시간 복잡도 로 매우 빠르며, 특히 ‘가중치가 없는 2차원 맵이나 그래프에서의 최단 거리/최소 횟수 탐색’ 문제의 치트키와도 같습니다. 코딩 테스트의 가장 든든한 무기이므로 완벽한 숙지가 필요합니다.

Graph View