[크래프톤 정글] BFS 개념 정리

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 또는 트리를 탐색하는 알고리즘 중 하나로, 가까운 노드부터 탐색을 진행하는 방식이다.

BFS의 기본 개념

1. 탐색 순서: BFS는 시작 정점에서부터 시작하여 인접한 모든 정점을 먼저 탐색한 후, 그다음으로 가까운 정점들로 확장해 나가는 방식이다. 이 과정을 반복하며 그래프를 탐색해 나간다.

2. 큐(Queue)를 이용한 구현: BFS는 큐(Queue) 자료구조를 사용해 구현한다. 큐는 FIFO(First In, First Out) 원칙에 따라 먼저 들어온 요소가 먼저 나가는 구조다. BFS는 정점을 탐색할 때 큐에 넣고, 큐에서 꺼내면서 그 정점의 인접한 정점을 다시 큐에 넣는 과정을 반복한다.

3. 방문 여부 체크: BFS는 같은 정점을 여러 번 방문하지 않도록 방문한 정점을 기록하는 visited 배열 또는 리스트를 사용한다. 이를 통해 무한 루프에 빠지지 않고 효율적으로 탐색할 수 있다.

BFS의 동작 방식

다음은 BFS가 어떻게 동작하는지를 단계별로 설명하겠다. 예제로 간단한 그래프를 사용하겠다.

예제 그래프

   1
  / \
 2   3
 |   |
 4   5

그래프는 총 5개의 노드(정점)와 4개의 간선으로 구성되어 있다. 이 그래프에서 노드 1을 시작점으로 BFS를 수행한다고 가정하자.

단계 1: 초기 설정

• 큐(Queue)를 생성하고, 탐색을 시작할 정점 1을 큐에 삽입한다.
• visited 리스트를 생성하고, 정점 1을 방문했음을 표시한다.

큐: [1]
visited: [1]

단계 2: 큐에서 첫 번째 정점을 꺼내고 인접한 정점을 탐색

• 큐에서 정점 1을 꺼내고, 이 정점에 인접한 정점 2와 3을 확인한다.
• 정점 2와 3은 아직 방문하지 않았으므로, 방문했다고 표시하고 큐에 추가한다.

큐: [2, 3]
visited: [1, 2, 3]

단계 3: 다음 정점을 꺼내고 인접한 정점을 탐색

• 큐에서 정점 2를 꺼내고, 인접한 정점 4를 확인한다.
• 정점 4는 아직 방문하지 않았으므로, 방문했다고 표시하고 큐에 추가한다.

큐: [3, 4]
visited: [1, 2, 3, 4]

단계 4: 다음 정점을 꺼내고 인접한 정점을 탐색

• 큐에서 정점 3을 꺼내고, 인접한 정점 5를 확인한다.
• 정점 5는 아직 방문하지 않았으므로, 방문했다고 표시하고 큐에 추가한다.

큐: [4, 5]
visited: [1, 2, 3, 4, 5]

단계 5: 마지막 정점들을 탐색

• 큐에서 정점 4를 꺼내지만, 더 이상 방문할 인접한 정점이 없다.
• 같은 방식으로 정점 5를 꺼내지만, 역시 더 이상 인접한 정점이 없다.

큐: []
visited: [1, 2, 3, 4, 5]

큐가 비어 있으므로, BFS 탐색이 종료된다.

BFS의 시간 복잡도

BFS의 시간 복잡도는 O(V + E)이다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다. 이는 각 정점을 한 번씩 방문하고, 각 간선을 한 번씩 탐색하기 때문이다.

BFS의 주요 특성

1. 최단 경로 탐색: BFS는 무가중치 그래프에서 최단 경로를 탐색할 때 사용된다. 모든 간선의 가중치가 동일할 때, BFS는 시작 정점에서 특정 정점까지의 최단 경로를 보장한다.

2. 모든 경로 탐색: BFS는 특정 정점에서 모든 다른 정점으로의 경로를 탐색하는 데 유용하다. 이를 통해 그래프가 연결되어 있는지(모든 정점이 연결되어 있는지) 확인할 수 있다.

3. 수평적 탐색: BFS는 깊이보다는 너비를 먼저 탐색하기 때문에, 한 정점에서 가까운 정점부터 차례로 탐색해 나가는 특징이 있다. 이는 트리의 레벨 오더 탐색(Level-Order Traversal)과 동일한 방식이다.

BFS의 구현 예제 (파이썬)

from collections import deque

def bfs(graph, start):
    visited = []  # 방문한 정점을 기록
    queue = deque([start])  # 큐를 생성하고 시작 정점을 삽입

    while queue:
        # 큐에서 정점을 하나 꺼냄
        node = queue.popleft()

        if node not in visited:
            visited.append(node)  # 정점을 방문했다고 기록

            # 인접한 정점들을 큐에 추가
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

    return visited

# 그래프 예제 (인접 리스트로 표현)
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 5],
    4: [2],
    5: [3]
}

# BFS 수행
visited_nodes = bfs(graph, 1)
print(visited_nodes)

예제 실행 결과:

[1, 2, 3, 4, 5]