너비 우선 탐색 알고리즘 (BFS)

8.1 BFS 알고리즘의 작동 원리

너비 우선 탐색 (Breadth-First Search, BFS)는 그래프를 순회하거나 탐색하는 알고리즘으로, 시작 정점에서 시작하여 현재 레벨에 있는 모든 인접 정점을 탐색한 후 다음 레벨의 정점으로 이동합니다.

알고리즘 단계:

1. 선택된 시작 정점에서 시작하여 큐에 넣습니다.
2. 큐가 빌 때까지 다음을 수행합니다:
   • 큐의 맨 앞에서 정점을 꺼내어 방문했다고 표시합니다.
   • 방문하지 않은 인접 정점을 모두 큐에 추가합니다.
3. 시작 정점에서 도달 가능한 모든 정점을 방문할 때까지 2단계를 반복합니다.

시각화:

시간 복잡도:

O(V + E) 여기서 V는 정점의 수, E는 간선의 수입니다.

그래프의 모든 노드와 간선은 한 번씩 방문됩니다.

공간 복잡도:

O(V), 큐에 정점을 저장하기 위해 사용되며, 상태(방문한 정점)를 저장하기 위한 배열도 사용됩니다.

8.2 큐를 활용한 BFS 구현

너비 우선 탐색은 큐와 같은 데이터 구조를 사용하면 효과적으로 구현됩니다.

큐를 사용한 BFS 구현:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # 노드 처리
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# 사용 예시:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 양방향 너비 우선 탐색

BFS는 종종 게임에서 두 지점 간의 최단 경로를 찾을 때 사용됩니다. 이러한 문제는 두 정점 사이의 그래프 경로 탐색 문제로 쉽게 변환됩니다. 그래프의 간선은 지도에서의 모든 통과 가능한 경로입니다.

하지만 더 빠르게 경로를 찾기 위해 두 끝에서 경로를 찾아야 합니다. 이를 위해 양방향 BFS가 사용됩니다.

작동 원리

양방향 너비 우선 탐색 (Bidirectional BFS)은 BFS를 최적화한 버전으로, 시작 정점과 목표 정점에서 각각 두 개의 병렬 그래프 순회를 수행합니다. 두 순회가 교차될 때까지 진행되며, 이는 전통적인 BFS에 비해 훨씬 적은 정점과 간선을 검사하도록 합니다.

알고리즘 단계:

• 시작 정점에서의 순회를 위한 큐와 목표 정점에서의 큐 두 개를 초기화합니다.
• 두 방향에서의 방문한 정점을 추적하기 위해 두 개의 방문 정점 집합을 초기화합니다.
• 두 큐로부터 번갈아 가며 그래프를 순회합니다.
• 각 단계에서 방문한 정점 집합이 교차하는지 확인합니다. 교차가 발견되면 경로가 존재합니다.
• 교차 노드가 발견되거나 큐가 빌 때까지 과정을 계속합니다.

시간 복잡도

최상의 경우: O(2 * (V + E)) = O(V + E), 여기서 V는 정점의 수, E는 간선의 수입니다.

양방향 BFS는 큰 그래프에서 단방향 BFS보다 일반적으로 더 적은 정점을 순회합니다.

공간 복잡도:

O(V) 두 큐와 두 개의 방문 정점 집합을 저장하기 위해 사용됩니다.

양방향 BFS의 예제 구현

예시는 매우 길기 때문에 단방향 탐색보다 세 배 정도 길어서 여기서는 생략합니다. 나중에 필요할 때는 스스로 작성할 수 있을 겁니다.

8.4 BFS를 사용하여 해결할 수 있는 문제 예시

BFS를 사용하여 해결할 수 있는 전형적인 문제 예시:

1. 무향 그래프에서 최단 경로 찾기:

BFS는 시작 정점에서 목표 정점까지의 최단 경로(최소 간선 수)를 찾는 데 사용됩니다.

적용 분야:

• 네비게이션 시스템에서 지점 간 최단 경로를 찾기 위해.
• 네트워크 분석에서 데이터 전송의 최단 경로를 찾기 위해.

2. 그래프 연결성 검사:

그래프가 연결되어 있는지, 즉 어떤 두 정점 사이에 경로가 존재하는지 확인.

적용 분야:

• 네트워크 분석에서 네트워크의 연결성을 확인하기 위해.
• 소셜 네트워크 분석에서 사용자 그룹의 연결성을 확인하기 위해.

3. 미로 생성:

BFS를 사용하여 주어진 속성을 가진 랜덤 미로 생성.

적용 분야:

• 게임 애플리케이션에서 미로를 생성하기 위해.
• 로봇 공학에서 내비게이션 알고리즘 테스트를 위해.

4. 트리에서 너비 우선 탐색:

BFS는 트리를 순회하여 트리의 각 레벨에서 작업을 수행하는 데 사용됩니다 (예: 각 레벨의 모든 노드 출력).

적용 분야:

• 데이터 시각화 문제에서 레벨별로 데이터를 표시해야 할 때.
• 계획 문제에서 계층 구조의 각 레벨에서 작업을 수행해야 할 때.

5. 이분 그래프 검사:

그래프가 이분 그래프인지, 즉 두 개의 집합으로 나눌 수 있고, 간선이 서로 다른 집합의 정점 사이에만 존재하는지를 확인.

적용 분야:

• 그래프 이론에서 그래프의 이분성을 확인하기 위해.
• 그래프 컬러링 문제에서 그래프를 두 가지 색으로 칠할 수 있는지 확인하기 위해.