개발이야기/파이썬

[알고리즘] BFS - 너비 우선 탐색

Study & Stack 2025. 6. 4. 00:49
728x90

BFS (Breadth-First Search): 너비 우선 탐색

BFS는 그래프 탐색 알고리즘의 하나로, 시작 노드에서 가장 가까운 노드들을 먼저 탐색하고, 그 다음 단계의 노드들을 탐색하는 방식입니다. 마치 돌멩이를 연못에 던졌을 때 물결이 동심원 형태로 퍼져나가는 것과 같다고 비유할 수 있습니다.

1. 핵심 개념:

  • 레벨(Level) 단위 탐색: 시작 노드로부터의 거리를 기준으로 '레벨'을 나누어 탐색합니다. 즉, 시작 노드(레벨 0)의 모든 이웃 노드(레벨 1)를 먼저 방문한 후, 레벨 1 노드들의 이웃 노드들(레벨 2)을 방문하는 식입니다.
  • 큐(Queue) 자료구조 사용: BFS는 탐색 순서를 관리하기 위해 큐(Queue) 자료구조를 핵심적으로 사용합니다. 큐는 '선입선출(FIFO: First-In, First-Out)' 방식으로 동작합니다. 즉, 먼저 들어간 요소가 먼저 나오는 방식입니다.

2. 작동 원리 (단계별 설명):

BFS의 작동 원리는 다음과 같은 단계로 이루어집니다.

  1. 시작 노드 설정 및 초기화:
    • 탐색을 시작할 노드를 선택합니다.
    • 방문할 노드를 저장할 queue (큐)를 생성하고, 시작 노드를 큐에 추가합니다.
    • 이미 방문한 노드를 기록할 visited (집합 또는 배열)를 생성하고, 시작 노드를 visited에 추가합니다. (중복 방문 방지)
  2. 큐가 빌 때까지 반복:
    • queue가 비어있지 않은 동안 다음 단계를 반복합니다.
  3. 노드 방문:
    • queue의 맨 앞에 있는 노드(현재 탐색할 노드)를 꺼냅니다 (popleft()).
    • 이 노드를 "방문"합니다. (예: 노드 값 출력, 특정 처리 수행 등)
  4. 인접 노드 탐색 및 큐에 추가:
    • 현재 방문한 노드의 모든 인접(이웃) 노드를 확인합니다.
    • 이웃 노드 중에서 아직 visited에 포함되지 않은 노드를 찾습니다.
    • 찾은 각 이웃 노드를 visited에 추가하고, queue의 뒤에 추가합니다 (append()).
  5. 탐색 종료:
    • queue가 비게 되면, 모든 연결된 노드를 탐색했음을 의미하며 BFS가 종료됩니다.

3. 파이썬 구현 예시:

collections 모듈의 deque를 사용하면 큐를 효율적으로 구현할 수 있습니다.

Python

from collections import deque

# 그래프를 인접 리스트로 표현 (딕셔너리 사용)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

def bfs(graph, start_node):
    # 1. 초기화
    visited = set()  # 방문한 노드를 저장할 집합
    queue = deque([start_node]) # 탐색할 노드를 저장할 큐. 시작 노드 삽입
    visited.add(start_node) # 시작 노드를 방문 처리

    print(f"BFS 탐색 시작 (시작 노드: {start_node}):")
    
    # 2. 큐가 빌 때까지 반복
    while queue:
        # 3. 노드 방문
        current_node = queue.popleft() # 큐에서 가장 먼저 들어온 노드 꺼내기
        print(f"  -> 방문: {current_node}") # 방문한 노드 출력 (예시)

        # 4. 인접 노드 탐색 및 큐에 추가
        for neighbor in graph[current_node]: # 현재 노드의 모든 이웃 노드 확인
            if neighbor not in visited: # 아직 방문하지 않은 이웃이라면
                visited.add(neighbor) # 방문 처리
                queue.append(neighbor) # 큐에 추가하여 나중에 방문하도록 함

    print("BFS 탐색 종료.")

# 예시 실행
bfs(graph, 'A')
# 예상 출력:
# BFS 탐색 시작 (시작 노드: A):
#   -> 방문: A
#   -> 방문: B
#   -> 방문: C
#   -> 방문: D
#   -> 방문: E
#   -> 방문: F
# BFS 탐색 종료.

4. BFS의 특징:

  • 최단 경로 보장 (가중치 없는 그래프에서): 간선에 가중치가 없는 그래프에서 BFS는 시작 노드로부터 각 노드까지의 **최단 거리(간선의 개수 기준)**를 보장합니다. 왜냐하면 시작 노드에서 한 칸 떨어진 모든 노드를 먼저 방문하고, 그 다음 두 칸 떨어진 노드를 방문하는 식으로 진행하기 때문입니다.
  • 완전 탐색: 연결된 모든 노드를 빠짐없이 탐색합니다.
  • 시간 복잡도:
    • 인접 리스트로 구현 시: O(V+E) (V: 노드 수, E: 간선 수). 모든 노드와 간선을 한 번씩만 방문하기 때문입니다.
    • 인접 행렬로 구현 시: O(V2). 각 노드에서 인접 노드를 찾기 위해 행렬의 모든 열을 확인해야 하기 때문입니다. (인접 리스트가 더 효율적인 경우가 많습니다.)
  • 공간 복잡도: O(V). 큐와 visited 집합에 최대 모든 노드가 저장될 수 있기 때문입니다.

5. BFS의 주요 활용 분야:

BFS는 다양한 문제 해결에 사용됩니다.

  • 최단 경로 찾기:
    • 가중치가 없는 그래프에서 최단 거리/경로 찾기는 BFS의 가장 대표적인 활용입니다. (예: 미로 찾기, 로봇이 특정 지점까지 이동하는 최소 단계 수)
    • "최소 이동 횟수", "가장 적은 비용", "가장 적은 단계" 등의 키워드가 문제에 등장하면 BFS를 고려해볼 수 있습니다.
  • 두 노드 사이의 최단 거리: 특정 두 노드 사이의 최단 거리를 찾는 데 사용됩니다.
  • 연결된 요소 (Connected Components) 찾기: 그래프 내에서 서로 연결된 노드들의 그룹을 찾는 데 사용됩니다.
  • 트리 레벨 순회 (Level Order Traversal): 트리 자료구조에서 각 레벨별로 노드를 순회할 때 사용됩니다.
  • 미로 찾기: 미로의 시작점에서 출구까지의 최단 경로를 찾는 데 활용됩니다.
  • 퍼즐 해결: 큐브 맞추기나 15-퍼즐과 같은 상태 공간 탐색 문제에서 최소 이동 횟수를 찾는 데 사용됩니다.
  • 네트워크 브로드캐스팅: 네트워크에서 한 지점에서 다른 모든 지점으로 메시지를 전파하는 최소 시간을 찾는 데 사용될 수 있습니다.
728x90