그래프 이론 - 3. 그래프 탐색 (Graph Traversal)

 

3. 그래프 탐색 (Graph Traversal)

3.1 깊이 우선 탐색(DFS, Depth-First Search)

📌 DFS 시간 및 공간 복잡도

• 시간 복잡도
  • 인접 행렬 사용 시: 𝑂(𝑁²) (모든 정점을 확인해야 함)
  • 인접 리스트 사용 시: 𝑂(𝑁+E) (정점과 간선 개수에 비례)
• 공간 복잡도
  • 𝑂(𝑁) (재귀 호출 또는 스택 사용)

---

3.2 너비 우선 탐색(BFS, Breadth-First Search)

📌 BFS 시간 및 공간 복잡도

• 시간 복잡도
  • 인접 행렬 사용 시: 𝑂(𝑁²)
  • 인접 리스트 사용 시: 𝑂(𝑁+E)
• 공간 복잡도
  • 𝑂(𝑁) (큐에 저장할 노드 개수)

---

📌 DFS vs BFS 미로 찾기 (경로 출력 기능 추가, 입/출력 예시 포함)

📌 미로 구조 예제

0 0 1 0
1 0 1 0
0 0 0 0

• 0: 이동 가능
• 1: 벽 (이동 불가능)
• 시작 위치: (0,0)
• 목표 위치: (2,3)

---

📌 DFS (깊이 우선 탐색) – 모든 경로 탐색

def dfs_maze(maze, x, y, visited, path):
    rows, cols = len(maze), len(maze[0])

    if x < 0 or y < 0 or x >= rows or y >= cols or maze[x][y] == 1 or (x, y) in visited:
        return False

    path.append((x, y))  # 현재 경로에 추가
    visited.add((x, y))

    if x == rows - 1 and y == cols - 1:  # 도착점
        print("DFS 경로:", path)
        return True

    # 상, 하, 좌, 우 탐색
    if (dfs_maze(maze, x + 1, y, visited, path) or
        dfs_maze(maze, x, y + 1, visited, path) or
        dfs_maze(maze, x - 1, y, visited, path) or
        dfs_maze(maze, x, y - 1, visited, path)):
        return True

    path.pop()  # 경로에서 제거 (백트래킹)
    return False

# 미로 정의
maze = [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0]
]

visited = set()
path = []
dfs_maze(maze, 0, 0, visited, path)

📌 출력 예시

DFS 경로: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3)]

---

📌 BFS (너비 우선 탐색) – 최단 경로 탐색

from collections import deque

def bfs_maze(maze):
    rows, cols = len(maze), len(maze[0])
    queue = deque([(0, 0, [(0, 0)])])  # (x, y, 경로)
    visited = set()

    while queue:
        x, y, path = queue.popleft()

        if (x, y) in visited or maze[x][y] == 1:
            continue

        visited.add((x, y))

        if x == rows - 1 and y == cols - 1:
            print("BFS 최단 경로:", path)
            return path  # 최단 경로 반환

        # 상, 하, 좌, 우 이동
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in visited:
                queue.append((nx, ny, path + [(nx, ny)]))

# 미로 탐색 실행
bfs_maze(maze)

📌 출력 예시

BFS 최단 경로: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3)]

---

✅ 최종 비교: DFS vs BFS 미로 탐색

알고리즘	탐색 방식	시간 복잡도	공간 복잡도	특징	활용 예제
DFS	깊이 우선 탐색	𝑂(𝑁+E) (인접 리스트), 𝑂(𝑁²) (인접 행렬)	𝑂(𝑁) (스택/재귀 사용)	모든 경로 탐색 가능, 백트래킹 사용	미로 탐색, 퍼즐 문제, 백트래킹
BFS	너비 우선 탐색	𝑂(𝑁+E) (인접 리스트), 𝑂(𝑁²) (인접 행렬)	𝑂(𝑁) (큐 사용)	최단 거리 보장 (가중치 없음)	최단 거리 문제, 네트워크 검색