Python 코딩테스트 04: BFS

너비 우선 탐색(BFS) 알고리즘: 이해와 응용

개요

BFS(Breadth-First Search)는 그래프나 트리 탐색 알고리즘 중 하나로, 넓이 우선 탐색이라고도 합니다.

이 알고리즘은 루트 노드에서 시작하여 인접한 노드들을 먼저 탐색한 후, 그 다음 깊이의 노드들을 탐색하는 방식입니다.

BFS는 주로 최단 경로 찾기나 레벨별 탐색에서 유용하게 사용됩니다.

이번 포스팅에서는 BFS의 원리, 구현 방법, 활용 예제 등을 자세히 설명하겠습니다.

 

BFS의 원리

BFS는 다음과 같은 단계로 진행됩니다:

1. 초기화: 탐색을 시작할 노드를 큐(queue)에 추가하고 방문 표시를 합니다.
2. 탐색: 큐에서 노드를 꺼내어 해당 노드의 인접한 노드들을 모두 큐에 추가합니다. 이때, 방문하지 않은 노드만 큐에 추가하고 방문 표시를 합니다.
3. 반복: 큐가 빌 때까지 2단계를 반복합니다.

BFS는 큐를 사용하여 구현하며, 각 레벨의 노드들을 순차적으로 방문합니다. 이로 인해 최단 경로를 찾는 데 매우 효율적입니다.

 

BFS의 단계별 예시

예시 그래프

다음과 같은 그래프가 있다고 가정해봅시다:

A - B - D
|   |
C - E

이 그래프에서 A 노드를 시작점으로 BFS를 수행해보겠습니다.

1. 초기화: 큐에 A를 추가하고 방문 표시합니다.

큐: [A] 방문: {A}

1. 큐에서 A를 꺼내고 인접한 노드 B, C를 큐에 추가합니다. 큐: [B, C] 방문: {A, B, C}
2. 큐에서 B를 꺼내고 인접한 노드 D, E를 큐에 추가합니다. 큐: [C, D, E] 방문: {A, B, C, D, E}
3. 큐에서 C를 꺼내고, C의 인접한 노드 B는 이미 방문했으므로 추가하지 않습니다. 큐: [D, E] 방문: {A, B, C, D, E}
4. 큐에서 D를 꺼내고, D의 인접한 노드는 이미 모두 방문했으므로 추가하지 않습니다. 큐: [E] 방문: {A, B, C, D, E}
5.  큐에서 E를 꺼내고, E의 인접한 노드 B, C는 이미 방문했으므로 추가하지 않습니다. 큐: [] 방문: {A, B, C, D, E}

큐가 비었으므로 BFS가 종료됩니다.

 

그림으로 보는 BFS

Initial Graph: 
A - B - D
|   |
C - E

BFS Traversal:
1. Start at A: Queue = [A], Visited = {A}
2. Visit B, C: Queue = [B, C], Visited = {A, B, C}
3. Visit D, E: Queue = [C, D, E], Visited = {A, B, C, D, E}
4. Visit remaining nodes: Queue = [], Visited = {A, B, C, D, E}

 

BFS의 구현

BFS는 주로 큐 자료구조를 사용하여 구현합니다.

BFS 코드 예시

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=' ')

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['B', 'C'],
}

# 예시 실행
bfs(graph, 'A')
# 출력: A B C D E

 

BFS의 특징

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 공간 복잡도: O(V) (큐에 최대 V개의 노드가 저장될 수 있음)
• 용도: 최단 경로 탐색, 레벨 순서 탐색 등

 

BFS의 활용

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

최단 경로 찾기

BFS는 무향 그래프나 가중치가 동일한 그래프에서 최단 경로를 찾는 데 유용합니다.

레벨 순서 탐색

트리 구조에서 각 레벨의 노드를 순차적으로 탐색할 때 사용됩니다.

 

예제: 최단 경로 찾기

다음은 BFS를 사용하여 최단 경로를 찾는 예제입니다.

def bfs_shortest_path(graph, start, goal):
    queue = deque([(start, [start])])
    visited = set()

    while queue:
        (vertex, path) = queue.popleft()
        for next in set(graph[vertex]) - set(path):
            if next == goal:
                return path + [next]
            else:
                queue.append((next, path + [next]))
                visited.add(vertex)
    return None

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['B', 'C'],
}

# 예시 실행
print(bfs_shortest_path(graph, 'A', 'D'))
# 출력: ['A', 'B', 'D']

 

결론

BFS는 그래프나 트리 탐색에서 널리 사용되는 알고리즘입니다.

큐를 이용한 넓이 우선 탐색을 통해 각 레벨의 노드를 순차적으로 탐색하고, 최단 경로를 효율적으로 찾을 수 있습니다.

BFS의 원리를 이해하고 다양한 문제에 적용하는 연습을 통해 효율적인 문제 해결 능력을 기를 수 있습니다.