[그래프 탐색: DFS와 BFS] 자료구조 탐색의 핵심 이해하기

그래프 탐색은 컴퓨터 과학에서 데이터를 탐색하거나 특정 경로를 찾기 위해 매우 중요한 개념입니다. 특히 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, Breadth First Search)은 대표적인 그래프 탐색 알고리즘입니다. 이번 포스트에서는 DFS와 BFS의 작동 원리, 차이점, 그리고 활용 사례를 알아보겠습니다.

 

---

1. 그래프란?

1) 정의

• 그래프(Graph)는 노드(Node)와 엣지(Edge)로 구성된 자료구조입니다.

• 노드는 데이터 또는 상태를 나타내고, 엣지는 노드 간의 관계를 나타냅니다.

2) 그래프의 유형

• 무방향 그래프: 엣지에 방향이 없음 (예: 친구 관계).

• 유방향 그래프: 엣지에 방향이 있음 (예: 트위터 팔로우).

• 가중 그래프: 엣지에 가중치가 있음 (예: 지도 거리).

3) 그래프의 표현 방식

• 인접 리스트(Adjacency List):

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [],
    4: [],
    5: []
}

• 인접 행렬(Adjacency Matrix):

  0  1  2  3  4  5
0 0  1  1  0  0  0
1 1  0  0  1  1  0
2 1  0  0  0  0  1
3 0  1  0  0  0  0
4 0  1  0  0  0  0
5 0  0  1  0  0  0

2. 깊이 우선 탐색 (DFS, Depth First Search)

1) 알고리즘 설명

• DFS는 하나의 경로를 끝까지 탐색한 후, 다른 경로로 이동하는 방식입니다.

• 주로 스택(Stack) 또는 재귀를 이용해 구현됩니다.

2) 특징

• 탐색 순서: 깊이 우선으로 방문.

• 시간 복잡도: O(V + E) (V: 노드 수, E: 엣지 수).

• 공간 복잡도: O(V) (스택이나 재귀 호출 스택 사용).

• 장점: 경로 탐색 문제, 순환 구조 탐색에 적합.

• 단점: 최단 경로를 보장하지 않음.

3) Python 코드

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')  # 방문 순서 출력
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 그래프 정의
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5],
    3: [],
    4: [],
    5: []
}

# 실행 예시
dfs(graph, 0)  # 출력: 0 1 3 4 2 5

3. 너비 우선 탐색 (BFS, Breadth First Search)

1) 알고리즘 설명

• BFS는 현재 노드와 인접한 노드를 먼저 탐색한 후, 다음 깊이로 이동하는 방식입니다.

• 큐(Queue)를 이용해 구현됩니다.

2) 특징

• 탐색 순서: 너비 우선으로 방문.

• 시간 복잡도: O(V + E).

• 공간 복잡도: O(V) (큐 사용).

• 장점: 최단 경로를 보장.

• 단점: 메모리 사용량이 많을 수 있음.

3) Python 코드

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        current = queue.popleft()
        print(current, end=' ')  # 방문 순서 출력
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 그래프 정의
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5],
    3: [],
    4: [],
    5: []
}

# 실행 예시
bfs(graph, 0)  # 출력: 0 1 2 3 4 5

4. DFS와 BFS의 차이점

특징	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방식	하나의 경로를 끝까지 탐색 후 다른 경로로 이동	인접한 모든 노드를 탐색 후 다음 깊이로 이동
구현 방식	스택 (재귀 또는 명시적 스택 사용)	큐
시간 복잡도	O(V + E)	O(V + E)
공간 복잡도	O(V)	O(V)
장점	경로 탐색에 적합, 메모리 사용량 적음	최단 경로 탐색에 적합, 탐색 순서 직관적
단점	최단 경로 보장하지 않음	메모리 사용량이 많을 수 있음
사용 사례	순환 탐지, 경로 탐색	최단 경로 탐색, 네트워크 탐색

5. 활용 사례

DFS 활용 사례

• 미로 찾기: 특정 출구까지의 경로를 찾기.

• 순환 탐지: 그래프에서 사이클이 존재하는지 확인.

• 백트래킹 문제: N-Queen, 퍼즐 문제.

BFS 활용 사례

• 최단 경로 탐색: 그래프에서 두 노드 간 최단 경로 찾기.

• 네트워크 확산: 바이러스 확산, 최단 거리 데이터 전송.

• 레벨 순회: 트리의 각 레벨에 있는 노드를 순서대로 출력.

6. 예제: DFS와 BFS의 탐색 순서

# 그래프 정의
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5],
    3: [],
    4: [],
    5: []
}

# DFS 실행
print("DFS 탐색 순서:")
dfs(graph, 0)  # 출력: 0 1 3 4 2 5

# BFS 실행
print("\nBFS 탐색 순서:")
bfs(graph, 0)  # 출력: 0 1 2 3 4 5