12.5 너비 우선 탐색(BFS)

12.5 너비 우선 탐색(BFS)

1. BFS의 개요

너비 우선 탐색(Breadth-First Search, BFS)은 그래프 탐색의 가장 기본적인 알고리즘 중 하나이며, 시작 노드에서 가까운 노드부터 차례로 방문한다. 큐(queue) 자료 구조를 사용하여 발견된 노드를 관리하며, 각 노드는 한 번만 방문된다. BFS는 비가중치 그래프에서 두 노드 사이의 최단 경로를 찾는 데 사용되며, 그래프의 연결성, 이분 그래프 검사, 레벨 순회 등 다양한 응용에 활용된다. 로봇공학에서는 격자 기반 경로 계획, 미로 탐색, 네트워크 분석 등에서 핵심적이다.

2. 알고리즘의 핵심 아이디어

2.1 너비 우선의 의미

BFS의 “너비 우선“은 시작 노드에서 한 단계 떨어진 노드들을 모두 방문한 후에 두 단계 떨어진 노드들을 방문하고, 이런 식으로 거리가 증가하는 순서로 노드를 방문한다는 의미이다.

2.2 큐의 역할

큐는 FIFO(First In, First Out) 원칙을 따르는 자료 구조이다. BFS에서 큐는 발견된 노드들을 거리 순서로 정렬하는 효과가 있다. 먼저 발견된 노드(가까운 노드)가 먼저 처리된다.

2.3 발견과 처리의 분리

BFS에서는 노드의 발견 시점과 처리 시점이 다르다.

  • 발견: 노드가 처음 인접 리스트에서 발견되는 시점
  • 처리: 노드가 큐에서 꺼내져 그 이웃들이 검사되는 시점

이러한 분리가 BFS의 정확성을 보장한다.

3. 알고리즘의 구체적 설명

3.1 의사 코드

BFS(G, s):
    // 초기화
    for each node v in G:
        v.distance = ∞
        v.parent = None
        v.discovered = false
    
    s.distance = 0
    s.discovered = true
    Q = empty queue
    Q.enqueue(s)
    
    // 메인 루프
    while Q is not empty:
        v = Q.dequeue()
        
        for each neighbor u of v:
            if not u.discovered:
                u.discovered = true
                u.distance = v.distance + 1
                u.parent = v
                Q.enqueue(u)

3.2 단계별 설명

  1. 초기화: 모든 노드의 거리를 무한대, 부모를 없음, 발견 표시를 거짓으로 설정한다.
  2. 시작: 시작 노드의 거리를 0으로 설정하고, 발견 표시를 참으로 변경한 후 큐에 추가한다.
  3. 반복: 큐가 비어있을 때까지 다음을 반복한다.
  • 큐에서 노드 v를 꺼낸다.
  • v의 모든 이웃 u에 대해, 아직 발견되지 않았으면 발견 표시하고 거리, 부모를 갱신한 후 큐에 추가한다.
  1. 종료: 모든 도달 가능한 노드가 처리되면 종료한다.

3.3 정확성

BFS의 정확성은 다음의 사실에 의해 보장된다.

  • 각 노드는 정확히 한 번 발견되고 큐에 추가된다.
  • 노드가 발견될 때의 거리는 최단 거리이다.
  • 큐에 있는 노드들의 거리는 단조 비감소 순서이다.

4. 시간 복잡도와 공간 복잡도

4.1 시간 복잡도

BFS의 시간 복잡도는 그래프의 표현 방법에 따라 다르다.

  • 인접 리스트: O(|V| + |E|)
  • 인접 행렬: O(|V|^2)

각 노드는 한 번 방문되고(O(|V|)), 각 엣지는 한 번 검사된다(O(|E|)).

4.2 공간 복잡도

공간 복잡도는 O(|V|)이다.

  • 큐의 크기: 최대 O(|V|)
  • 발견 표시: O(|V|)
  • 거리와 부모 정보: O(|V|)

5. BFS의 정확성 증명

5.1 거리 정리

BFS의 가장 중요한 성질은 다음과 같다.

정리: BFS가 시작 노드 s에서 노드 v를 발견하면, v.\text{distance}는 s에서 v로의 최단 거리(엣지 수)와 같다.

5.2 증명 개요

이 정리는 귀납법으로 증명된다. 거리가 k인 모든 노드가 BFS에 의해 정확한 거리로 발견됨을 보인다.

  1. 기저: s.\text{distance} = 0이며, 이는 자명하게 정확하다.
  2. 귀납 단계: 거리 k의 모든 노드가 정확히 발견된다고 가정한다. 거리 k+1의 노드 v는 거리 k의 어떤 노드 u의 이웃이며, u가 처리될 때 v가 발견되어 거리 k+1로 표시된다.

5.3 큐의 단조성

큐에 있는 노드들의 거리는 다음의 성질을 만족한다.

  • Q = (v_1, v_2, \ldots, v_n)에 대해 v_1.\text{distance} \leq v_2.\text{distance} \leq \cdots \leq v_n.\text{distance}
  • v_n.\text{distance} \leq v_1.\text{distance} + 1

이러한 성질이 BFS의 정확성과 효율성을 보장한다.

6. BFS의 주요 응용

6.1 비가중치 최단 경로

BFS의 가장 직접적인 응용은 비가중치 그래프에서의 최단 경로 찾기이다.

from collections import deque

def bfs_shortest_path(G, s, t):
    if s == t:
        return [s]
    
    visited = {s}
    parent = {s: None}
    Q = deque([s])
    
    while Q:
        v = Q.popleft()
        for u in G[v]:
            if u not in visited:
                visited.add(u)
                parent[u] = v
                if u == t:
                    return reconstruct_path(parent, t)
                Q.append(u)
    
    return None  # 경로가 없음

def reconstruct_path(parent, t):
    path = []
    while t is not None:
        path.append(t)
        t = parent[t]
    return path[::-1]

6.2 모든 노드까지의 거리

BFS는 시작 노드에서 모든 도달 가능한 노드까지의 거리를 계산한다.

def bfs_distances(G, s):
    distances = {s: 0}
    Q = deque([s])
    
    while Q:
        v = Q.popleft()
        for u in G[v]:
            if u not in distances:
                distances[u] = distances[v] + 1
                Q.append(u)
    
    return distances

6.3 연결 성분 찾기

BFS를 사용하여 무방향 그래프의 연결 성분을 찾을 수 있다.

def connected_components(G):
    visited = set()
    components = []
    
    for v in G.nodes:
        if v not in visited:
            component = bfs(G, v)
            components.append(component)
            visited.update(component)
    
    return components

def bfs(G, s):
    visited = {s}
    Q = deque([s])
    component = [s]
    
    while Q:
        v = Q.popleft()
        for u in G[v]:
            if u not in visited:
                visited.add(u)
                component.append(u)
                Q.append(u)
    
    return component

6.4 이분 그래프 검사

BFS를 사용하여 그래프가 이분 그래프인지 검사할 수 있다.

def is_bipartite(G):
    color = {}
    
    for start in G.nodes:
        if start in color:
            continue
        color[start] = 0
        Q = deque([start])
        
        while Q:
            v = Q.popleft()
            for u in G[v]:
                if u not in color:
                    color[u] = 1 - color[v]
                    Q.append(u)
                elif color[u] == color[v]:
                    return False
    
    return True

6.5 레벨 순회

BFS는 트리의 레벨 순회와 같다. 같은 레벨의 노드들이 순서대로 방문된다.

7. BFS의 변형

7.1 다중 시작점 BFS

여러 시작 노드에서 동시에 BFS를 시작할 수 있다. 모든 노드까지의 가장 가까운 시작 노드의 거리를 계산한다.

def multi_source_bfs(G, sources):
    distances = {s: 0 for s in sources}
    Q = deque(sources)
    
    while Q:
        v = Q.popleft()
        for u in G[v]:
            if u not in distances:
                distances[u] = distances[v] + 1
                Q.append(u)
    
    return distances

응용: 여러 화재 시작점에서 모든 위치까지의 가장 가까운 화재까지의 거리.

7.2 양방향 BFS

양방향 BFS(bidirectional BFS)는 시작 노드와 목표 노드에서 동시에 BFS를 시작하여 만나는 점에서 종료한다. 검색 공간을 크게 줄인다.

def bidirectional_bfs(G, s, t):
    if s == t:
        return [s]
    
    visited_s = {s: None}
    visited_t = {t: None}
    Q_s = deque([s])
    Q_t = deque([t])
    
    while Q_s and Q_t:
        # 시작점에서 한 단계
        if Q_s:
            v = Q_s.popleft()
            for u in G[v]:
                if u in visited_t:
                    return reconstruct_bidirectional(visited_s, visited_t, v, u)
                if u not in visited_s:
                    visited_s[u] = v
                    Q_s.append(u)
        
        # 목표점에서 한 단계
        if Q_t:
            v = Q_t.popleft()
            for u in G[v]:
                if u in visited_s:
                    return reconstruct_bidirectional(visited_s, visited_t, u, v)
                if u not in visited_t:
                    visited_t[u] = v
                    Q_t.append(u)
    
    return None

이 방법은 검색 트리의 크기를 줄여 계산 시간을 단축한다.

7.3 -1 BFS

엣지 가중치가 0 또는 1인 그래프에서는 0-1 BFS가 사용된다. 덱(deque)을 사용하며, 가중치 0인 엣지는 앞에, 가중치 1인 엣지는 뒤에 추가한다.

8. 격자 그래프에서의 BFS

8.1 격자 그래프

격자 그래프는 행과 열로 구성된 노드들의 집합이며, 인접한 셀이 엣지로 연결된다. 모바일 로봇의 경로 계획에서 자주 사용된다.

8.2 방향 vs 8방향

격자 그래프의 인접성은 두 가지로 정의된다.

  • 4방향: 상, 하, 좌, 우의 4개 이웃
  • 8방향: 4방향 + 4개의 대각선 이웃

응용에 따라 적절한 인접성을 선택한다.

8.3 격자 BFS

def grid_bfs(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    if grid[start[0]][start[1]] == 1 or grid[goal[0]][goal[1]] == 1:
        return None  # 시작 또는 목표가 장애물
    
    visited = {start}
    parent = {start: None}
    Q = deque([start])
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while Q:
        r, c = Q.popleft()
        if (r, c) == goal:
            return reconstruct_path(parent, goal)
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    parent[(nr, nc)] = (r, c)
                    Q.append((nr, nc))
    
    return None  # 경로 없음

8.4 응용

격자 BFS는 다음과 같은 응용에서 사용된다.

  • 모바일 로봇의 경로 계획
  • 미로 탐색
  • 게임 캐릭터의 이동
  • 이미지 처리의 영역 채우기

9. BFS와 DFS의 비교

9.1 메모리 사용

BFS는 같은 깊이의 모든 노드를 큐에 저장해야 하므로, 너비가 큰 그래프에서는 메모리 사용이 많다. DFS는 깊이에 비례하는 메모리만 사용한다.

9.2 최단 경로

BFS는 비가중치 그래프에서 최단 경로를 보장한다. DFS는 보장하지 않는다.

9.3 응용

응용BFSDFS
비가중치 최단 경로예아니오
모든 노드 방문예예
사이클 검출가능더 자연스러움
위상 정렬가능 (Kahn)더 자연스러움
연결 성분둘 다 가능둘 다 가능

10. 실제 구현 시 고려사항

10.1 효율적인 자료 구조

큐의 효율적인 구현이 중요하다. Python에서는 collections.deque가 양 끝에서 O(1)의 연산을 제공한다.

10.2 발견 표시

발견 표시는 해시 셋이나 비트 배열로 구현할 수 있다. 그래프의 크기에 따라 선택한다.

10.3 메모리 관리

큰 그래프에서는 메모리 사용을 모니터링해야 한다. 큐가 너무 커지면 메모리 부족이 발생할 수 있다.

10.4 종료 조건

목표 노드를 찾는 BFS는 목표 노드에 도달하면 즉시 종료할 수 있다. 모든 노드를 방문하는 BFS는 큐가 비어있을 때까지 계속한다.

11. BFS의 라이브러리 지원

11.1 NetworkX

import networkx as nx

G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4)])

# BFS 트리
T = nx.bfs_tree(G, source=1)

# BFS 엣지 순회
for edge in nx.bfs_edges(G, source=1):
    print(edge)

# 최단 경로
path = nx.shortest_path(G, source=1, target=4)

11.2 다른 라이브러리

  • igraph
  • Boost Graph Library
  • graph-tool

12. 응용 예시: 모바일 로봇의 경로 계획

청소 로봇이 방의 시작 위치에서 목표 위치까지 이동할 때 BFS가 사용된다. 방을 격자로 분할하고, 각 셀이 노드, 인접 셀이 엣지가 된다. 장애물이 있는 셀은 그래프에서 제외된다.

13. 응용 예시: 미로 탐색

미로의 입구에서 출구까지의 가장 짧은 경로를 찾는 데 BFS가 사용된다. 미로의 셀이 노드, 통과 가능한 인접 셀이 엣지이다.

14. 응용 예시: 친구 추천

소셜 네트워크에서 친구의 친구 등을 추천할 때 BFS가 사용된다. 시작 사용자에서 일정 거리 내의 사용자들이 후보가 된다.

15. 응용 예시: 화재 시뮬레이션

건물에서 화재가 시작되었을 때 시간에 따른 화재의 확산을 시뮬레이션하는 데 다중 시작점 BFS가 사용된다.

16. 응용 예시: 웹 크롤링

웹 크롤러가 페이지를 발견 순서대로 방문할 때 BFS가 사용된다. 시작 페이지에서 가까운 페이지부터 크롤링한다.

17. 성능 최적화

17.1 캐시 친화성

큰 그래프에서는 메모리 접근 패턴이 성능에 영향을 준다. 캐시 친화적인 자료 구조 배치가 중요하다.

17.2 병렬 BFS

BFS는 같은 레벨의 노드들을 병렬로 처리할 수 있다. GPU 기반 병렬 BFS가 큰 그래프에서 효과적이다.

17.3 분산 BFS

큰 그래프는 여러 컴퓨터에 분산되어 처리된다. 분산 BFS는 통신 비용을 최소화해야 한다.

18. 학습의 가치

BFS를 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

  • 그래프 알고리즘의 가장 기본적인 도구를 익힌다.
  • 비가중치 최단 경로 문제를 해결할 수 있다.
  • 다양한 그래프 분석 작업을 수행할 수 있다.
  • 더 복잡한 알고리즘(다익스트라, A*)의 기초를 형성한다.
  • 로봇 경로 계획의 기본을 이해한다.

19. 학습 권장사항

19.1 직접 구현

BFS를 처음부터 직접 구현해 보는 것이 가장 좋은 학습 방법이다. 다양한 그래프(연결, 비연결, 사이클 포함, 격자 등)에 적용해 본다.

19.2 시각화

BFS의 단계별 시각화는 알고리즘의 동작을 이해하는 데 매우 유용하다. 큐의 상태와 발견된 노드들이 시각화된다.

19.3 변형 학습

다중 시작점 BFS, 양방향 BFS, 0-1 BFS 등의 변형을 학습한다. 각 변형이 어떤 응용에 적합한지 이해한다.

20. 본 절의 의의

본 절은 그래프 알고리즘의 가장 기본적이고 중요한 BFS를 자세히 다루었다. BFS는 그 자체로 유용할 뿐만 아니라, 더 복잡한 알고리즘의 기초이며, 로봇공학의 다양한 응용에서 핵심적으로 활용된다.

21. 참고 문헌

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
  • Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
  • LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
  • Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
  • Moore, E. F. (1959). “The shortest path through a maze.” Proceedings of the International Symposium on the Theory of Switching, 285–292.

version: 1.0