알고리즘 그래프 탐색 - BFS(너비 우선 탐색)

오늘은 그래프의 탐색 방법 중 BFS(너비 우선 탐색)에 대해 알아 보겠다. 

BFS(너비 우선 탐색)

BFS(Breadth-First Search, 너비 우선 탐색)은 그래프 탐색 알고리즘 중의 하나이다. 한 노드에서 시작하여 인접한 모든 노드를 먼저 탐색한 후, 그 다음 레벨의 노드를 탐색하는 방식이다. 그래프나 트리 구조를 탐색할 때 사용되며, 보통 큐(Queue) 자료구조를 사용한다. 

 

핵심 메커니즘

• BFS는 시작 노드로부터 가까운 노드부터 차례대로 탐색한다. 즉, 현재 레벨의 모든 노드를 탐색한 후에 다음 레벨로 이동한다.
• BFS는 일반적으로 큐 자료구조를 사용하여 구현된다. 이는 FIFO(First In, First Out) 원칙을 따르므로 노드를 방문한 순서대로 처리할 수 있다.
• BFS는 가중치 없는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 자동으로 찾는다. 

 

작동 방식

 

1. Step 1 (레벨 0):
   1. 시작 노드 A를 방문한다. 
   2. 방문한 노드: A
2. Step 2 (레벨 1):
   1. A의 모든 인접 노드인 B와 C를 방문한다. 
   2. 방문한 노드: A, B, C
3. Step 3 (레벨 2):
   1. B의 인접 노드인 D와 E를 방문한다.
   2. C의 인접 노드인 F를 방문한다. 
   3. 방문한 노드: A, B, C, D, E, F
4. Step 4 (완료):
   1. 모든 노드를 방문했으므로 BFS가 완료된다. 
   2. 최종 방문 순서: A, B, C, D, E, F

 

인접 리스트로 표현하기 - 딕셔너리

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

 

파이썬으로 코드 구현하기 - 큐

# deque를 사용하여 큐를 효율적으로 구현합니다. 
# deque는 양쪽에서 빠르게 추가/제거가 가능한 자료구조입니다.
from collections import deque

def bfs(graph, start):
    # 방문한 노드를 추적하기 위한 집합입니다. 
    # 집합(set)을 사용하면 중복 방지와 빠른 검색이 가능합니다.
    visited = set()  
    
    # 탐색을 위한 큐를 초기화합니다. 시작 노드를 큐에 넣습니다.
    # deque([start])는 start를 포함하는 새로운 deque 객체를 생성합니다.
    queue = deque([start])
    
    # 시작 노드를 방문했다고 표시합니다.
    visited.add(start)

    # 큐가 비어있지 않은 동안 계속 반복합니다.
    # 큐가 비어있다는 것은 모든 접근 가능한 노드를 탐색했다는 의미입니다.
    while queue:  
        # 큐의 왼쪽(앞쪽)에서 노드를 하나 꺼냅니다. 
        # 이는 가장 먼저 큐에 들어간 노드, 즉 현재 레벨에서 가장 먼저 발견된 노드입니다.
        node = queue.popleft()
        
        # 현재 처리 중인 노드를 출력합니다. end=' '는 줄바꿈 대신 공백을 출력하게 합니다.
        print(node, end=' ')  

        # 현재 노드의 모든 이웃 노드들을 확인합니다.
        # graph[node]는 현재 노드와 연결된 모든 노드의 리스트입니다.
        for neighbor in graph[node]:
            # 이웃 노드가 아직 방문되지 않았다면
            if neighbor not in visited:
                # 이웃 노드를 방문했다고 표시합니다.
                visited.add(neighbor)
                # 이웃 노드를 큐의 오른쪽(뒤쪽)에 추가합니다.
                # 이렇게 하면 현재 레벨의 모든 노드를 처리한 후에 다음 레벨로 넘어갑니다.
                queue.append(neighbor)

# 그래프를 인접 리스트 형태로 표현합니다.
# 각 키는 노드를, 값은 해당 노드와 연결된 노드들의 리스트를 나타냅니다.
graph = {
    'A': ['B', 'C'],  # A 노드는 B, C와 연결되어 있습니다.
    'B': ['A', 'D', 'E'],  # B 노드는 A, D, E와 연결되어 있습니다.
    'C': ['A', 'F'],  # C 노드는 A, F와 연결되어 있습니다.
    'D': ['B'],  # D 노드는 B와 연결되어 있습니다.
    'E': ['B'],  # E 노드는 B와 연결되어 있습니다.
    'F': ['C']   # F 노드는 C와 연결되어 있습니다.
}

# 'A'를 시작 노드로 하여 BFS를 실행합니다.
bfs(graph, 'A')

 

코드의 특징

• deque를 사용하여 큐를 구현했다. 이는 양쪽에서의 빠른 삽입과 삭제(O(1) 시간)를 가능하게 한다. 
• set을 사용하여 방문한 노드를 추적한다. 이로 인해 노드의 방문 여부 확인이 O(1) 시간에 가능하다. 
• 그래프를 인접 리스트 형태의 딕셔너리로 표현했다. 이는 메모리 효율적이며, 각 노드의 이웃을 쉽게 접근할 수 있게 한다. 
• visited 집합을 사용하여 이미 방문한 노드를 다시 큐에 넣지 않도록 했다. 이는 무한 루프를 방지하고, 각 노드를 정확히 한 번만 방문하게 한다. 
• 큐를 사용함으로써 노드들을 레벨 순서대로 탐색한다. 즉, 시작 노드로부터의 거리가 가까운 노드부터 차례로 탐색한다. 

 

큐 없이 구현하는 방법

① 리스트를 사용한 구현

def bfs(graph, start):
    visited = set()  # 방문한 노드를 추적하기 위한 집합
    to_visit = [start]  # 방문할 노드들의 리스트. 시작 노드로 초기화
    visited.add(start)  # 시작 노드를 방문했다고 표시

    while to_visit:  # 방문할 노드가 남아있는 동안 반복
        node = to_visit.pop(0)  # 리스트의 첫 번째 요소를 제거하고 반환
        print(node, end=' ')  # 현재 처리 중인 노드 출력

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                to_visit.append(neighbor)  # 이웃 노드를 방문할 노드 리스트의 끝에 추가

# 그래프 정의
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

# BFS 실행
bfs(graph, 'A')

 

주요 변경사항 

• collections import deque를 제거했다.
  더 이상 deque 자료 구조를 사용하지 않기 때문이다. 파이썬의 기본 list를 사용하여 BFS를 구현하기로 결정했으므로 deque 모듈을 가져올 필요가 없어졌다. 
• queue = deque([start]) 대신 to_visit = [start]를 사용한다.
  deque 대신 일반 파이썬 list를 사용하기로 했기 때문이다. list는 파이썬의 기본 자료구조로, 별도의 import 없이 사용할 수 있다. 변수명을 queue에서 to_visit으로 변경하여 그 목적을 더 명확히 했다. 
• node = queue.popleft() 대신 node = to_visit.pop(0)를 사용한다. 
  eque의 popleft() 메서드는 왼쪽 끝의 요소를 제거하고 반환한다.  list에는 popleft() 메서드가 없으므로, 대신 pop(0)을 사용한다. pop(0)은 리스트의 첫 번째 요소(인덱스 0)를 제거하고 반환하므로, popleft()와 동일한 기능을 수행한다. 

이 구현은 기능적으로 이전 코드와 동일하게 작동하지만, 성능 면에서는 차이가 있을 수 있다. to_visit.pop(0)는 O(n) 시간 복잡도를 가지므로, 큰 그래프에서는 deque를 사용하는 것이 더 효율적일 수 있다. 하지만 작은 그래프나 교육 목적으로는 이 방식도 충분히 유효하다. 

 

생각해볼 점

lsit.pop(0)가 O(n) 시간 복잡도를 가지는 이유

첫 번째 요소를 제거할 때, 나머지 모든 요소들을 한 칸씩 앞으로 이동시켜야 한다. 리스트의 크기가 n이라면, n-1개의 요소를 이동시켜야 한다. 따라서 이 이동 작업이 O(n) 시간이 걸리므로, 전체 연산의 시간 복잡도가 O(n)이 된다. 

 

list.pop(0)와 deque.popleft()의 차이

 

특성	list.pop(0)	deque.popleft()
시간 복잡도	O(n)	O(1)
내부 구현	동적 배열	이중 연결 리스트
메모리 사용	연속적	분산적
첫 요소 제거 시	나머지 요소 이동 필요	포인터만 조정
대규모 데이터 처리	비효율적	효율적
임의 접근	O(1)	O(n)

 

list.pop(0)는 모든 요소를 이동시켜야 하므로 O(n) 시간이 걸린다. deque.popleft()는 첫 노드의 포인터만 조정하면 되므로 O(1) 시간에 수행된다. deque는 양방향 연결 리스트로 구현되어 있어 첫 요소 제거가 매우 빠르다. list는 연속된 메모리를 사용하지만, deque는 분산된 메모리를 사용한다. 

 

 

② 재귀를 사용한 구현

def recursive_bfs(graph, to_visit, visited=None):
    if visited is None:
        visited = set()

    if not to_visit:  # 기저 조건: 방문할 노드가 없으면 종료
        return

    node = to_visit.pop(0)  # 현재 노드 가져오기
    print(node, end=' ')  # 현재 노드 출력

    # 현재 노드의 이웃들을 방문 목록에 추가
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            to_visit.append(neighbor)

    # 재귀적으로 다음 노드 방문
    recursive_bfs(graph, to_visit, visited)

# 그래프 정의 (이전과 동일)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

# BFS 실행
start_node = 'A'
recursive_bfs(graph, [start_node], set([start_node]))

주요 특징 

• recursive_bfs 함수는 그래프, 방문할 노드 리스트, 그리고 이미 방문한 노드 집합을 매개변수로 받는다.
• 기저 조건(base case)은 방문할 노드가 없을 때 (if not to_visit) 함수를 종료하는 것이다.
• 현재 노드를 처리하고 (출력), 그 이웃들을 방문 목록에 추가한다.
• 재귀 호출을 통해 다음 노드를 처리한다. 

 

주의할 점 

• 재귀 호출은 콜 스택을 사용하므로, 큰 그래프에서는 스택 오버플로우가 발생할 수 있다.
• 재귀 호출은 각 호출마다 새로운 스택 프레임을 생성하므로, 반복적 방법보다 더 많은 메모리를 사용할 수 있다. 

 

생각해볼 점

① 큐는 BFS 구현에 가장 적합한 자료구조다. → 왜그럴까?

큐의 선입선출 FIFO(First-In-First-Out) 구조가 그래프의 레벨 순서 탐색을 자연스럽게 구현하여, 현재 노드와 가까운 노드부터 순차적으로 방문할 수 있게 해준다.

 

② BFS 알고리즘의 구현의 시간 복잡도는 O(V + E)이다(여기서 V는 노드의 수, E는 간선의 수). → 왜 그럴까?

모든 노드와 간선을 한 번씩 방문하기 때문이다.