큐를 이용한 BFS 구현

안녕하세요, 여러분! 오늘은 알고리즘의 세계에서 매우 중요한 위치를 차지하고 있는 ‘너비 우선 탐색(Breadth-First Search, BFS)‘에 대해 알아보려고 합니다. BFS는 그래프나 트리 구조를 탐색하는 방법 중 하나로, 특히 큐(Queue)를 이용해 구현됩니다. 처음 들어보시는 분들도 계실 텐데요, 걱정 마세요. 아주 쉽고 재미있게 설명해 드리겠습니다.

먼저, BFS가 무엇인지 간단히 설명드릴게요. BFS는 시작 지점에서 가까운 노드부터 차례대로 탐색해 나가는 방법입니다. 마치 물결이 퍼져나가듯이, 시작점에서 가까운 곳부터 동심원을 그리며 탐색 범위를 넓혀갑니다. BFS는 레벨별로 노드를 탐색해 나갑니다. 큐를 사용하기 때문에 먼저 발견된 노드가 먼저 탐색되는 것이 특징입니다.

이제 파이썬으로 BFS를 구현해 볼까요? BFS를 구현할 때는 큐와 방문 여부를 체크하는 리스트(또는 집합)가 필요합니다.

파이썬의 collections 모듈에 있는 deque를 사용하면 큐를 효율적으로 구현할 수 있습니다. 그럼 이제 BFS를 파이썬으로 구현해 볼까요?

from collections import deque

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

    while queue:  # 큐가 빌 때까지 반복
        current_node = queue.popleft()  # 큐에서 노드를 하나 꺼냄
        print(current_node, end=' ')  # 현재 노드 출력

        # 현재 노드와 연결된 모든 노드에 대해
        for neighbor in graph[current_node]:
            if neighbor not in visited:  # 아직 방문하지 않은 이웃 노드라면
                queue.append(neighbor)  # 큐에 추가
                visited.add(neighbor)  # 방문 처리

# 그래프 정의 (인접 리스트 방식)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

print("BFS 탐색 결과:")
bfs(graph, 'A')  # A를 시작 노드로 BFS 실행

이 코드를 자세히 살펴볼까요?

visited 집합: 이미 방문한 노드를 저장합니다. 집합(set)을 사용하면 중복을 피하고 빠르게 검색할 수 있습니다.
queue: 탐색할 노드를 저장하는 큐입니다. deque를 사용하여 효율적으로 구현했습니다.
while queue:: 큐가 빌 때까지 반복합니다. 이는 모든 연결된 노드를 탐색할 때까지 계속됩니다.
current_node = queue.popleft(): 큐에서 노드를 하나 꺼냅니다. 이 노드가 현재 탐색 중인 노드가 됩니다.
for neighbor in graph[current_node]:: 현재 노드와 연결된 모든 이웃 노드를 확인합니다.
if neighbor not in visited:: 아직 방문하지 않은 이웃 노드라면, 큐에 추가하고 방문 처리를 합니다.

이 BFS 구현의 시간 복잡도는 O(V + E)입니다. 여기서 V는 노드의 수, E는 간선의 수입니다. 모든 노드와 간선을 한 번씩 확인하기 때문입니다.

이제 이 BFS 알고리즘이 어떻게 동작하는지 단계별로 살펴볼까요? 위의 그래프를 예로 들어 설명해 드리겠습니다.

시작 노드 ‘A’를 큐에 넣고 방문 처리합니다. 큐: [‘A’], 방문: {‘A’}
‘A’를 큐에서 꺼내고, ‘A’의 이웃 노드 ‘B’와 ‘C’를 큐에 넣고 방문 처리합니다. 큐: [‘B’, ‘C’], 방문: {‘A’, ‘B’, ‘C’}
‘B’를 큐에서 꺼내고, ‘B’의 이웃 노드 중 방문하지 않은 ‘D’와 ‘E’를 큐에 넣고 방문 처리합니다. 큐: [‘C’, ‘D’, ‘E’], 방문: {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}
‘C’를 큐에서 꺼내고, ‘C’의 이웃 노드 중 방문하지 않은 ‘F’와 ‘G’를 큐에 넣고 방문 처리합니다. 큐: [‘D’, ‘E’, ‘F’, ‘G’], 방문: {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}
‘D’, ‘E’, ‘F’, ‘G’를 순서대로 큐에서 꺼냅니다. 이들의 이웃 노드는 모두 이미 방문했으므로 더 이상 큐에 노드를 추가하지 않습니다.
큐가 비어있으므로 알고리즘이 종료됩니다.

최종 탐색 순서: A B C D E F G

이 과정을 통해 BFS가 어떻게 그래프를 레벨 단위로 탐색해 나가는지 알 수 있습니다.

BFS의 특징과 장단점을 정리해볼까요?

장점

최단 경로 찾기: 가중치가 없는 그래프에서 최단 경로를 찾을 수 있습니다.
레벨 단위 탐색: 시작 노드로부터의 거리에 따라 노드를 탐색합니다.
무한 그래프에서도 사용 가능: 깊이 우선 탐색(DFS)과 달리, 무한히 긴 경로가 있어도 최단 경로를 찾을 수 있습니다.

단점

메모리 사용: 큐에 많은 노드를 저장해야 할 수 있어 메모리 사용량이 많을 수 있습니다.
가중치가 있는 그래프: 간선에 가중치가 있는 경우, 최단 경로를 찾지 못할 수 있습니다.

BFS는 다양한 실제 문제에 적용될 수 있습니다. 몇 가지 예를 들어볼까요?

소셜 네트워크에서의 ‘친구 추천’ 기능: 현재 사용자와 가까운 관계에 있는 사람들을 찾을 때 사용할 수 있습니다.
네비게이션 시스템: 두 지점 간의 최단 경로를 찾을 때 사용될 수 있습니다.
웹 크롤링: 웹 페이지를 탐색할 때, 시작 페이지에서 링크를 따라 점점 멀리 이동하면서 정보를 수집할 수 있습니다.
퍼즐 풀이: 루빅스 큐브나 슬라이딩 퍼즐 같은 문제에서 최소 이동으로 목표 상태에 도달하는 방법을 찾을 때 사용될 수 있습니다.
네트워크 브로드캐스트: 네트워크에서 정보를 효율적으로 모든 노드에 전파할 때 사용될 수 있습니다.

여러분, 이제 BFS에 대해 어느 정도 이해가 되셨나요? 처음에는 조금 복잡해 보일 수 있지만, 실제로 구현해보면 생각보다 간단하다는 것을 알 수 있을 거예요. BFS는 그래프 탐색의 기본이 되는 알고리즘이므로, 잘 이해해두면 앞으로 더 복잡한 그래프 문제를 해결하는 데 큰 도움이 될 거예요.

연습 삼아 다양한 그래프에 BFS를 적용해보는 건 어떨까요? 예를 들어, 미로 탈출 문제를 BFS로 해결해보거나, 체스판에서 나이트의 최소 이동 경로를 찾는 문제를 풀어보세요. 이런 문제들을 통해 BFS의 활용법을 더 깊이 이해할 수 있을 거예요.

BFS는 그래프 이론의 기초가 되는 중요한 알고리즘입니다. 이를 잘 이해하고 활용하면 복잡한 문제도 효율적으로 해결할 수 있게 됩니다. 앞으로 알고리즘 문제를 풀거나 프로그램을 개발할 때 BFS를 활용할 수 있는 상황이 없는지 한 번씩 생각해보세요. 여러분의 문제 해결 능력이 한층 더 성장할 거예요!

다음에는 BFS와 쌍을 이루는 또 다른 중요한 그래프 탐색 알고리즘인 ‘깊이 우선 탐색(Depth-First Search, DFS)‘에 대해 알아보는 것도 좋을 것 같아요.