너비 우선 탐색(BFS) 완벽 가이드: 이론부터 Python 구현까지

너비 우선 탐색_{(BFS, Breadth-First Search)}은 그래프 또는 트리 자료 구조에서 많이 사용되는 탐색 알고리즘이다. BFS는 시작 노드에서부터 시작해 인접한 노드를 먼저 모두 방문한 뒤, 그 다음으로 인접한 노드를 방문하는 방식으로 작동한다. 즉, 깊게 탐색하기보다는 넓게 탐색하는 것이 BFS의 특징이다.

이번 포스트에서는 BFS의 이론적 개념부터 관련 자료 구조, Python으로 구현하는 방법까지 자세히 알아보도록 하자.

BFS의 이론적 배경

너비 우선 탐색_(BFS)은 그래프나 트리 구조에서 노드를 탐색하는 효율적인 방법 중 하나이다. BFS는 첫 번째로 방문한 노드와 인접한 모든 노드를 먼저 방문한 뒤, 그 다음 레벨의 노드들을 차례로 방문한다. 이러한 방식은 모든 노드를 넓이 우선으로 탐색할 때 유용하며, 최단 경로를 찾는 문제에서도 자주 사용된다.

BFS의 주요 특징

방문 순서

BFS는 먼저 가까운 노드를 방문한 후, 점점 멀리 있는 노드를 방문하는 방식으로 진행된다.

최단 경로

BFS는 탐색 경로의 각 간선의 가중치가 동일한 그래프에서 시작 노드와 목표 노드 간의 최단 경로를 찾는 데 적합하다.

큐(Queue) 사용

BFS는 탐색 과정에서 노드를 저장하고 관리하기 위해 큐 자료 구조를 사용한다. 큐는 FIFO_{(First In, First Out)} 구조로, 먼저 추가된 노드가 먼저 처리된다.

완전성

BFS는 유한한 그래프에서 모든 노드를 방문한다.

자료 구조

BFS를 구현하기 위해서는 몇 가지 중요한 자료 구조를 알아야 한다.

그래프_(Graph)

그래프는 노드_(Node)와 그 노드를 연결하는 간선_(Edge)으로 이루어져 있다.
BFS에서는 그래프의 각 노드와 간선을 순차적으로 방문하며, 그래프는 인접 리스트_{(Adjacency list)}나 인접 행렬_{(Adjacency matrix)}로 표현될 수 있다.

큐_(Queue)

BFS는 큐를 사용하여 탐색 순서를 관리한다.
큐는 FIFO 구조로, 먼저 큐에 들어간 노드가 먼저 처리되며, 탐색을 위해 각 노드를 큐에 차례로 추가한다.

방문 표시(Visited)

BFS에서는 이미 방문한 노드를 다시 방문하지 않기 위해 방문 여부를 기록하는 것이 중요하다.
보통 리스트(List)나 집합(Set)을 사용해 방문한 노드를 추적한다.

BFS의 동작 과정

BFS는 다음과 같은 단계로 동작한다.

1. 탐색 시작 노드를 큐에 추가하고 방문했다고 표시한다.
2. 큐에서 노드를 하나씩 꺼내어 해당 노드를 방문한다.
3. 현재 노드에서 갈 수 있는 모든 인접 노드를 큐에 추가한다_{(이미 방문한 노드는 제외)}.
4. 큐가 빌 때까지 이 과정을 반복한다.

BFS의 Python 구현

BFS를 Python으로 구현하는 방법을 알아보자.
이 구현에서는 큐 자료 구조를 사용하여 너비 우선 탐색을 수행한다.

from collections import deque

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

# BFS 함수
def bfs(start_node):
    visited = set()  # 방문한 노드를 기록할 집합
    queue = deque([start_node])  # 탐색 시작 노드를 큐에 추가

    while queue:
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        if node not in visited:
            print(node, end=' ')  # 방문한 노드를 출력
            visited.add(node)  # 노드를 방문한 것으로 표시
            queue.extend(graph[node])  # 인접한 노드들을 큐에 추가

# BFS 시작
bfs('A')

코드 설명

• graph: 그래프는 인접 리스트로 표현되며, 각 노드의 인접한 노드를 리스트로 정의한다.
• bfs 함수: 이 함수는 큐를 사용하여 BFS를 수행한다. 큐에서 노드를 하나씩 꺼내 방문 여부를 확인하고, 방문하지 않은 경우 그 노드를 방문한 후 인접한 노드를 큐에 추가한다.
• queue: 큐는 탐색할 노드를 저장하는 자료 구조이다. 여기서는 시작 노드를 먼저 큐에 추가하고, 그 후 인접한 노드를 순서대로 큐에 넣어 너비 우선 탐색을 수행한다.

BFS의 활용 사례

BFS는 다양한 문제에서 활용될 수 있다.

• 최단 경로 탐색: 가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 찾는 문제에 효과적이다.
• 그래프 탐색: 그래프에서 특정 조건을 만족하는 노드를 찾거나 전체 그래프를 탐색하는 데 유용하다.
• 네트워크 연결성 확인: 네트워크에서 연결된 모든 노드를 방문하여 연결성을 확인하는 데 사용할 수 있다.
• 미로 탐색: 미로에서 출구까지의 최단 경로를 찾는 문제에도 BFS가 자주 사용된다.

결론

이번 포스트에서는 너비 우선 탐색_(BFS)에 대해 이론적 배경부터 자료 구조, 그리고 Python으로 구현하는 방법까지 자세히 설명해 보았다. BFS는 그래프와 트리 탐색에서 매우 중요한 알고리즘이며, 특히 최단 경로를 찾는 문제에서 큰 장점을 발휘한다. 제공된 예제 코드를 통해 BFS의 동작 방식을 이해하고, 다양한 문제에 적용해 보시길 바란다.