4-4. 그래프 탐색: BFS (너비 우선 탐색)

1. BFS (너비 우선 탐색) 소개

그래프 탐색 알고리즘은 그래프 자료구조에서 특정 노드를 찾는 방법, 또는 그래프의 모든 노드를 방문하는 방법을 의미합니다. 그래프 탐색은 다양한 문제 해결의 핵심 요소이며, 특히 최단 경로 탐색, 네트워크 분석, 게임 맵 탐색 등 광범위한 분야에서 활용됩니다. DFS (깊이 우선 탐색)와 BFS (너비 우선 탐색)는 가장 기본적인 그래프 탐색 알고리즘입니다.

BFS는 그래프의 너비를 우선적으로 탐색하는 방식으로, 시작 노드에서 인접한 모든 노드를 먼저 방문한 후, 해당 노드들의 인접 노드를 차례로 방문하는 방식입니다. 마치 연못에 돌을 던졌을 때 파문이 퍼져나가는 것과 유사한 방식으로 동작합니다. 이러한 특성 덕분에 BFS는 최단 경로 탐색 문제에 효과적으로 사용됩니다.

2. BFS의 동작 원리

BFS는 큐(Queue) 자료구조를 활용하여 구현됩니다. 큐는 FIFO (First-In, First-Out) 구조를 가지며, 먼저 들어온 데이터가 먼저 나가는 방식으로 동작합니다. BFS는 다음과 같은 단계를 거칩니다.

1. 시작 노드 큐에 삽입: 탐색을 시작할 노드를 큐에 넣고, 방문 처리합니다.
2. 큐에서 노드 추출 및 인접 노드 탐색: 큐에서 노드를 하나 꺼냅니다. 해당 노드의 인접 노드들을 확인합니다.
3. 미방문 노드 큐에 삽입: 인접 노드 중 방문하지 않은 노드를 큐에 넣고, 방문 처리합니다.
4. 반복: 큐가 빌 때까지 2, 3단계를 반복합니다.

이러한 과정을 통해 BFS는 시작 노드로부터 모든 노드를 너비 우선으로 탐색합니다. 각 단계에서 큐에 들어가는 노드는 현재 레벨의 노드들이며, 이 레벨의 모든 노드가 처리된 후 다음 레벨의 노드들이 큐에 추가됩니다.

3. BFS 구현

BFS는 프로그래밍 언어의 큐 자료구조를 활용하여 쉽게 구현할 수 있습니다. 다음은 Python을 사용한 BFS 구현 예시입니다.

from collections import deque

def bfs(graph, start_node):
  """
  BFS 알고리즘 구현

  Args:
    graph: 그래프 (인접 리스트)
    start_node: 시작 노드
  """
  visited = set()  # 방문한 노드를 추적하기 위한 집합
  queue = deque([start_node])  # 큐 (deque 사용)
  visited.add(start_node)

  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': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
}

위의 그래프와 start_node = 'A'로 bfs(graph, 'A')를 호출하면, 출력 결과는 A B C D E F가 됩니다. 이는 BFS가 노드를 방문하는 순서를 보여줍니다.

4. BFS의 시간 복잡도

BFS의 시간 복잡도는 그래프의 표현 방식에 따라 달라집니다. 일반적으로 인접 리스트를 사용하는 경우, 시간 복잡도는 $O(V + E)$ 입니다. 여기서 $V$는 노드의 수, $E$는 간선의 수를 의미합니다.

• 각 노드는 큐에 한 번씩 들어가고 한 번씩 나오므로, $O(V)$의 시간이 소요됩니다.
• 각 간선은 최대 한 번씩 탐색되므로, $O(E)$의 시간이 소요됩니다.

인접 행렬을 사용하는 경우에는 각 노드의 인접 노드를 확인하기 위해 모든 노드를 순회해야 하므로 $O(V^2)$의 시간 복잡도를 가집니다.

5. BFS와 큐 (Queue)

BFS는 큐를 핵심 자료구조로 사용합니다. 큐는 BFS의 탐색 순서를 결정하고, 각 노드를 방문하는 순서를 관리합니다. 큐는 FIFO 구조를 따르므로, 먼저 큐에 들어간 노드부터 탐색이 이루어집니다. 이는 시작 노드에서 가까운 노드부터 탐색하는, 즉 너비 우선 탐색의 핵심 원리를 구현하는 데 기여합니다.

6. BFS의 활용

BFS는 다음과 같은 다양한 문제 해결에 활용될 수 있습니다.

1. 최단 경로 탐색: 가중치가 없는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾을 수 있습니다.
2. 그래프의 연결 요소 찾기: 그래프의 모든 노드를 방문하여 연결된 컴포넌트를 식별할 수 있습니다.
3. 미로 탐색: 미로에서 시작 지점으로부터 출구까지의 최단 경로를 찾을 수 있습니다.
4. 소셜 네트워크 분석: 특정 사용자와 다른 사용자 간의 최소 연결 거리를 파악할 수 있습니다.

7. BFS 활용 예제: 최단 경로 탐색

가중치가 없는 그래프에서 최단 경로를 찾는 문제를 예시로 들어보겠습니다. 시작 노드에서 각 노드까지의 최단 거리를 구하는 문제입니다.

from collections import deque

def shortest_path(graph, start_node):
  """
  BFS를 활용한 최단 경로 탐색

  Args:
    graph: 그래프 (인접 리스트)
    start_node: 시작 노드

  Returns:
    distances: 시작 노드로부터 각 노드까지의 최단 거리
  """
  distances = {node: -1 for node in graph} # 초기 거리: -1 (방문 X)
  distances[start_node] = 0 # 시작 노드 거리는 0
  queue = deque([start_node])

  while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
      if distances[neighbor] == -1: # 방문하지 않은 노드
        distances[neighbor] = distances[node] + 1
        queue.append(neighbor)
  return distances

위 코드는 shortest_path 함수를 구현하여 BFS를 사용하여 최단 거리를 계산합니다. distances 딕셔너리는 시작 노드로부터 각 노드까지의 최단 거리를 저장합니다. -1은 방문하지 않은 노드를 의미합니다. BFS를 통해 각 노드를 방문하면서, 시작 노드로부터의 거리를 갱신합니다.

예시 그래프:

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

만약 shortest_path(graph, 'A')를 호출한다면, 반환되는 distances는 다음과 같습니다.

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

이 결과는 각 노드까지의 최단 거리를 나타냅니다. 예를 들어, 노드 'D'까지의 최단 거리는 2입니다.

8. BFS의 장단점

1) 장점

• 최단 경로 보장: 가중치가 없는 그래프에서 최단 경로를 효율적으로 찾을 수 있습니다.
• 구현 용이성: 큐를 사용하여 비교적 쉽게 구현할 수 있습니다.
• 메모리 효율성: DFS에 비해 메모리 사용량이 적을 수 있습니다 (그래프의 형태에 따라 다름).

2) 단점

• 메모리 사용량: 그래프의 모든 노드를 큐에 저장해야 하므로, 그래프가 크고 밀집된 경우 메모리 사용량이 증가할 수 있습니다.
• 가중치 그래프: 가중치가 있는 그래프에서는 BFS를 직접 사용할 수 없으며, Dijkstra 알고리즘과 같은 다른 알고리즘을 사용해야 합니다.

9. DFS vs BFS 비교

DFS와 BFS는 그래프 탐색의 기본적인 두 가지 접근 방식입니다. 각 알고리즘은 탐색 방식, 적용 분야, 시간 복잡도에서 차이를 보입니다.

10. 결론

BFS는 그래프 탐색의 핵심 알고리즘 중 하나로, 너비 우선 탐색을 통해 최단 경로 문제, 그래프 연결 요소 탐색 등 다양한 문제를 해결하는 데 사용됩니다. 큐 자료구조를 활용하여 구현이 용이하며, 가중치가 없는 그래프에서 효율적인 성능을 보입니다. BFS의 원리를 이해하고, 적절한 문제에 적용함으로써 효율적인 문제 해결 능력을 향상시킬 수 있습니다.