12.4 그래프 탐색 알고리즘의 기본 원리

12.4 그래프 탐색 알고리즘의 기본 원리

1. 그래프 탐색의 개요

그래프 탐색(graph search 또는 graph traversal)은 그래프의 모든 노드(또는 일부 노드)를 체계적으로 방문하는 알고리즘이다. 가장 기본적이고 중요한 그래프 알고리즘이며, 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)의 두 주요 방법이 있다. 그래프 탐색은 그 자체로 유용할 뿐만 아니라, 더 복잡한 알고리즘(최단 경로, 연결 성분, 사이클 검출, 위상 정렬 등)의 기반이 된다. 로봇공학에서는 경로 계획, 환경 탐색, 상태 공간 탐색 등에 핵심적으로 활용된다.

2. 탐색의 기본 개념

2.1 탐색의 정의

그래프 탐색은 시작 노드에서 출발하여 그래프의 노드들을 체계적으로 방문하는 과정이다. 각 노드는 한 번만 방문되어야 하며, 모든 도달 가능한 노드를 방문해야 한다.

2.2 탐색의 목적

탐색의 목적은 응용에 따라 다양하다.

  • 모든 노드 방문: 그래프 전체의 정보 수집
  • 특정 노드 찾기: 검색 문제
  • 경로 찾기: 두 노드 사이의 경로 발견
  • 연결성 확인: 두 노드가 연결되어 있는지 확인
  • 그래프 구조 분석: 사이클, 컴포넌트 등의 분석

2.3 방문과 발견

탐색 과정에서 두 가지 상태가 구분된다.

  • 발견: 노드를 처음 본 시점
  • 방문: 노드를 처리한 시점 (모든 이웃을 살펴본 후)

이 두 시점이 알고리즘의 분석에 중요하다.

3. 탐색 알고리즘의 일반 형태

3.1 일반 탐색

대부분의 그래프 탐색 알고리즘은 다음의 일반 형태를 따른다.

1. 시작 노드를 자료 구조에 추가하고 발견 표시
2. 자료 구조가 비어있지 않은 동안:
    a. 자료 구조에서 노드 v를 꺼냄
    b. v의 처리 (방문)
    c. v의 모든 이웃에 대해:
        - 발견되지 않은 이웃이면 자료 구조에 추가하고 발견 표시
3. 종료

자료 구조의 종류(큐 vs 스택)가 BFS와 DFS를 구분한다.

3.2 자료 구조의 선택

자료 구조알고리즘동작
큐(FIFO)BFS가까운 노드부터 방문
스택(LIFO)DFS깊이 있게 방문
우선순위 큐Best-first search우선순위에 따라 방문

4. 너비 우선 탐색 (BFS)

4.1 개념

너비 우선 탐색(Breadth-First Search, BFS)은 시작 노드에서 가까운 노드부터 방문하는 알고리즘이다. 큐를 사용하여 노드를 관리한다.

4.2 알고리즘

BFS(G, s):
    Q = empty queue
    visited = {s}
    Q.enqueue(s)
    
    while Q is not empty:
        v = Q.dequeue()
        process(v)
        for each neighbor u of v:
            if u not in visited:
                visited.add(u)
                Q.enqueue(u)

4.3 특성

BFS의 주요 특성은 다음과 같다.

  • 시작 노드에서 가까운 노드부터 방문한다.
  • 비가중치 그래프에서 최단 경로를 찾는다.
  • 발견된 순서가 시작 노드에서의 거리 순서와 같다.

4.4 시간 복잡도

BFS의 시간 복잡도는 다음과 같다.

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

각 노드는 한 번 방문되고, 각 엣지는 한 번 검사된다.

4.5 공간 복잡도

큐의 최대 크기는 O(|V|)이며, 발견 표시도 O(|V|)이다.

5. 깊이 우선 탐색 (DFS)

5.1 개념

깊이 우선 탐색(Depth-First Search, DFS)은 가능한 한 깊이 들어간 후 돌아오는 방식으로 탐색하는 알고리즘이다. 스택(또는 재귀)을 사용한다.

5.2 재귀적 구현

DFS(G, v):
    visited.add(v)
    process(v)
    for each neighbor u of v:
        if u not in visited:
            DFS(G, u)

5.3 반복적 구현

DFS_iterative(G, s):
    stack = [s]
    visited = {s}
    
    while stack is not empty:
        v = stack.pop()
        process(v)
        for each neighbor u of v:
            if u not in visited:
                visited.add(u)
                stack.push(u)

5.4 특성

DFS의 주요 특성은 다음과 같다.

  • 깊이 있게 한 경로를 따라간다.
  • 백트래킹(backtracking)으로 다른 경로를 탐색한다.
  • 재귀적 구조가 자연스럽다.
  • 스택 깊이가 그래프의 깊이에 비례한다.

5.5 시간 복잡도

DFS의 시간 복잡도는 BFS와 같다.

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

5.6 공간 복잡도

DFS의 공간 복잡도는 O(|V|)이지만, 재귀 스택의 깊이가 그래프의 깊이에 비례하므로 깊은 그래프에서는 스택 오버플로우의 위험이 있다.

6. BFS와 DFS의 비교

6.1 방문 순서

측면BFSDFS
자료 구조큐 (FIFO)스택 (LIFO)
방문 순서너비 우선깊이 우선
최단 경로비가중치 그래프보장 안 함
메모리너비에 비례깊이에 비례
응용최단 경로, 레벨 순회사이클 검출, 위상 정렬

6.2 적합한 응용

6.2.1 BFS의 적합한 응용

  • 비가중치 그래프의 최단 경로
  • 레벨 순회
  • 두 노드 사이의 가장 짧은 경로
  • 웹 크롤링 (가까운 페이지부터)

6.2.2 DFS의 적합한 응용

  • 사이클 검출
  • 위상 정렬
  • 강하게 연결된 컴포넌트
  • 다리(bridge)와 절단점(articulation point)
  • 미로 탐색

7. BFS의 응용

7.1 최단 경로

비가중치 그래프에서 BFS는 두 노드 사이의 최단 경로를 찾는다. 발견된 순서가 거리 순서와 일치한다.

BFS_shortest_path(G, s, t):
    distance = {s: 0}
    parent = {s: None}
    Q = [s]
    
    while Q is not empty:
        v = Q.pop(0)
        if v == t:
            return reconstruct_path(parent, t)
        for u in G[v]:
            if u not in distance:
                distance[u] = distance[v] + 1
                parent[u] = v
                Q.append(u)

7.2 연결 성분

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

def find_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

7.3 이분 그래프 검사

BFS를 사용하여 그래프가 이분 그래프인지 검사할 수 있다. 인접한 노드를 다른 색으로 칠한다.

8. DFS의 응용

8.1 사이클 검출

DFS를 사용하여 그래프에 사이클이 있는지 검사할 수 있다. 방향 그래프에서는 백 엣지(back edge)의 존재가 사이클을 의미한다.

def has_cycle(G):
    color = {v: 'white' for v in G.nodes}  # 미발견
    
    def dfs(v):
        color[v] = 'gray'  # 처리 중
        for u in G[v]:
            if color[u] == 'gray':  # 백 엣지
                return True
            if color[u] == 'white' and dfs(u):
                return True
        color[v] = 'black'  # 완료
        return False
    
    for v in G.nodes:
        if color[v] == 'white':
            if dfs(v):
                return True
    return False

8.2 위상 정렬

방향 비순환 그래프(DAG)의 위상 정렬은 DFS를 사용하여 구현할 수 있다. DFS의 완료 순서의 역순이 위상 순서이다.

def topological_sort(G):
    visited = set()
    order = []
    
    def dfs(v):
        visited.add(v)
        for u in G[v]:
            if u not in visited:
                dfs(u)
        order.append(v)
    
    for v in G.nodes:
        if v not in visited:
            dfs(v)
    
    return order[::-1]

8.3 강하게 연결된 컴포넌트

방향 그래프의 강하게 연결된 컴포넌트(SCC)를 찾는 알고리즘에는 Kosaraju 알고리즘과 Tarjan 알고리즘이 있다. 둘 다 DFS를 사용한다.

9. 탐색의 변형

9.1 이중 BFS

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

9.2 IDDFS

반복 깊이 우선 탐색(Iterative Deepening DFS, IDDFS)은 깊이 제한 DFS를 점진적으로 깊이를 증가시키며 반복한다. BFS의 메모리 효율성과 DFS의 메모리 효율성을 결합한다.

9.3 이분 검색

이분 검색은 정렬된 트리에서 효율적인 검색을 제공한다. 이진 검색 트리, AVL 트리, B-트리 등이 사용된다.

10. 가중치 그래프에서의 탐색

10.1 Best-First Search

Best-First Search는 우선순위 큐를 사용하여 평가 함수가 가장 좋은 노드부터 방문한다. 이는 Dijkstra와 A* 알고리즘의 기초이다.

10.2 다익스트라 알고리즘

다익스트라(Dijkstra) 알고리즘은 가중치 그래프에서 단일 시작점 최단 경로를 찾는다. BFS의 일반화이다.

10.3 A* 알고리즘

A* 알고리즘은 휴리스틱 함수를 사용하여 효율적인 최단 경로 탐색을 수행한다. AI와 로봇공학에서 표준이다.

11. 탐색의 성능 분석

11.1 시간 복잡도

알고리즘시간 복잡도
BFS, DFS (인접 리스트)O(\vert V\vert + \vert E\vert)
BFS, DFS (인접 행렬)O(\vert V\vert^2)
다익스트라 (이진 힙)O((\vert V\vert + \vert E\vert)\log\vert V\vert)
다익스트라 (피보나치 힙)O(\vert V\vert\log\vert V\vert + \vert E\vert)
벨만-포드O(\vert V\vert\vert E\vert)

11.2 공간 복잡도

대부분의 탐색 알고리즘의 공간 복잡도는 O(|V|)이다. 자료 구조(큐, 스택, 우선순위 큐)와 발견 표시가 주요 메모리 사용이다.

12. 탐색의 최적화

12.1 시각적 최적화

탐색 과정을 시각화하면 알고리즘의 동작을 이해하는 데 도움이 된다. 단계별 시각화 도구가 있다.

12.2 병렬 탐색

병렬 탐색은 여러 프로세서를 사용하여 탐색을 가속한다. BFS는 자연스럽게 병렬화 가능하다.

12.3 분산 탐색

분산 탐색은 여러 컴퓨터에서 큰 그래프를 탐색한다. MapReduce 등의 프레임워크가 사용된다.

13. 응용

13.1 미로 탐색

미로 탐색은 가장 직관적인 그래프 탐색 응용이다. 미로의 셀이 노드, 인접 셀이 엣지이다. BFS는 최단 경로를, DFS는 임의의 경로를 찾는다.

13.2 웹 크롤링

웹 크롤링은 웹페이지(노드)와 링크(엣지)를 탐색한다. BFS가 일반적이지만, 우선순위에 따른 탐색도 사용된다.

13.3 소셜 네트워크 분석

소셜 네트워크에서 친구의 친구를 찾거나, 가장 가까운 사람을 찾는 데 BFS가 사용된다.

13.4 컴파일러

컴파일러의 의존성 분석에 위상 정렬이 사용된다. 사이클 검출은 순환 의존성을 발견한다.

14. 로봇공학에서의 응용

14.1 격자 환경의 경로 계획

모바일 로봇이 격자로 분할된 환경에서 목표 위치까지의 경로를 찾을 때 BFS, DFS, A* 등이 사용된다.

14.2 구성 공간 탐색

매니퓰레이터의 구성 공간(configuration space)을 탐색하여 충돌 없는 경로를 찾는다. 샘플링 기반 방법(PRM, RRT)이 그래프 탐색의 변형이다.

14.3 작업 계획

로봇의 작업 계획에서 상태 공간을 탐색한다. 상태가 노드, 행동이 엣지이다.

14.4 SLAM

SLAM에서 회로 폐쇄 검출에 그래프 검색이 사용된다. 후보 노드와의 매칭이 검색 문제이다.

14.5 다중 로봇 협조

다중 로봇이 환경을 함께 탐색할 때 분산 탐색 알고리즘이 사용된다.

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

청소 로봇이나 배달 로봇이 실내 환경에서 목표 위치까지 이동할 때 그래프 탐색이 사용된다. 환경을 격자로 분할하고, 장애물을 제외한 셀들이 그래프의 노드가 된다.

def plan_path(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    visited = {start}
    Q = [(start, [start])]
    
    while Q:
        (r, c), path = Q.pop(0)
        if (r, c) == goal:
            return path
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                Q.append(((nr, nc), path + [(nr, nc)]))
    
    return None  # 경로 없음

16. 응용 예시: 매니퓰레이터의 구성 공간 탐색

매니퓰레이터의 구성 공간에서 시작 자세에서 목표 자세까지의 경로를 찾을 때 RRT(Rapidly-exploring Random Tree)가 사용된다. 트리에 새 노드를 추가하면서 그래프를 구축한다.

17. 응용 예시: 작업 의존성

매니퓰레이션 작업의 의존성을 그래프로 표현한 후, 위상 정렬로 작업 순서를 결정한다. 사이클 검출로 의존성의 일관성을 검증한다.

18. 응용 예시: 게임 AI

체스, 바둑 등의 게임 AI에서 가능한 수의 트리를 탐색한다. 미니맥스 알고리즘과 알파-베타 가지치기가 DFS의 변형이다.

19. 응용 예시: 장애물 회피

자율 주행 차량의 장애물 회피에서 가능한 운동의 그래프를 탐색하여 안전한 경로를 찾는다.

20. 학습의 가치

그래프 탐색 알고리즘의 기본 원리를 이해하는 것은 다음과 같은 이점을 제공한다.

  • 다양한 그래프 알고리즘의 기초를 익힌다.
  • 로봇 경로 계획과 작업 계획의 알고리즘을 이해할 수 있다.
  • 효율적인 탐색 전략을 설계할 수 있다.
  • 학술 문헌과 산업 표준을 이해할 수 있다.
  • 새로운 알고리즘을 개발할 수 있다.

21. 학습 권장사항

21.1 직접 구현

BFS와 DFS를 직접 구현해 보는 것이 이해에 도움이 된다. 다양한 그래프에 적용해 본다.

21.2 시각화

알고리즘의 단계별 시각화는 이해를 깊게 한다. 다양한 시각화 도구가 있다.

21.3 응용 학습

로봇공학의 실제 응용에 알고리즘을 적용해 본다. 격자 환경의 경로 계획, 미로 탐색 등이 좋은 시작이다.

22. 본 절의 의의

본 절은 그래프 탐색의 기본 원리와 두 주요 알고리즘(BFS, DFS)을 다루었다. 이러한 알고리즘은 후속 절에서 다루는 더 복잡한 알고리즘의 기반이며, 로봇공학의 다양한 응용에서 핵심적이다.

23. 참고 문헌

  • 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.
  • Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
  • LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.

version: 1.0