4-5. 그래프 탐색: DFS와 BFS 비교

1. DFS(Depth-First Search)와 BFS(Breadth-First Search) 개요

그래프 탐색 알고리즘은 그래프 자료구조의 모든 노드(node)를 방문하는 방법입니다. DFS와 BFS는 그래프 탐색의 대표적인 두 가지 접근 방식이며, 각각 다른 방식으로 노드를 탐색합니다. 이 두 알고리즘은 다양한 문제 해결에 사용되며, 각 알고리즘의 특성을 이해하는 것은 문제 해결 능력 향상에 매우 중요합니다.

DFS는 깊이 우선 탐색으로, 한 경로(path)를 최대한 깊이 탐색한 후, 더 이상 탐색할 노드(node)가 없으면 다른 경로(path)로 이동하는 방식입니다. BFS는 너비 우선 탐색으로, 시작 노드(node)에서 인접한 모든 노드(node)를 먼저 방문한 후, 그 다음 레벨의 노드(node)들을 방문하는 방식입니다.

2. DFS 상세 분석

1) 동작 방식

DFS는 스택(stack) 또는 재귀 호출을 사용하여 구현됩니다. 스택을 사용하는 경우, 탐색할 노드(node)를 스택에 넣고, 스택에서 노드(node)를 꺼내면서 해당 노드(node)의 인접 노드(node)들을 스택에 다시 넣는 방식으로 진행됩니다. 재귀 호출을 사용하는 경우, 현재 노드(node)를 방문하고, 해당 노드(node)의 인접 노드(node)들을 재귀적으로 호출하는 방식으로 구현됩니다.

2) 시간 복잡도

DFS의 시간 복잡도는 그래프의 표현 방식에 따라 달라집니다. 인접 행렬(adjacency matrix)로 그래프를 표현하는 경우, 각 노드(node)의 모든 노드(node)를 확인해야 하므로 시간 복잡도는 $O(V^2)$입니다. 여기서 $V$는 노드(node)의 수입니다. 인접 리스트(adjacency list)로 그래프를 표현하는 경우, 각 노드(node)의 인접 노드(node)만 확인하면 되므로 시간 복잡도는 $O(V + E)$입니다. 여기서 $E$는 간선(edge)의 수입니다.

3) 공간 복잡도

DFS의 공간 복잡도는 스택 또는 재귀 호출의 깊이에 따라 달라집니다. 최악의 경우, 모든 노드(node)를 방문해야 하므로 공간 복잡도는 $O(V)$입니다.

4) DFS의 특징

• DFS는 한 경로(path)를 끝까지 탐색하므로, 해(solution)가 깊숙한 곳에 있는 경우 BFS보다 더 빠르게 찾을 수 있습니다.
• DFS는 재귀 호출을 사용하기 때문에, 코드 구현이 간결하다는 장점이 있습니다.
• DFS는 스택 오버플로우(stack overflow)가 발생할 수 있으므로, 재귀 호출 깊이에 제한이 있는 경우 주의해야 합니다.

3. BFS 상세 분석

1) 동작 방식

BFS는 큐(queue)를 사용하여 구현됩니다. 시작 노드(node)를 큐에 넣고, 큐에서 노드(node)를 꺼내면서 해당 노드(node)의 인접 노드(node)들을 큐에 넣는 방식으로 진행됩니다. 큐에 넣어진 노드(node)들은 큐의 특성상 먼저 들어온 순서대로 처리됩니다.

2) 시간 복잡도

BFS의 시간 복잡도는 DFS와 마찬가지로 그래프 표현 방식에 따라 달라집니다. 인접 행렬을 사용하는 경우 시간 복잡도는 $O(V^2)$이며, 인접 리스트를 사용하는 경우 $O(V + E)$입니다.

3) 공간 복잡도

BFS의 공간 복잡도는 큐에 저장되는 노드(node)의 수에 따라 달라집니다. 최악의 경우, 모든 노드(node)가 큐에 저장될 수 있으므로 공간 복잡도는 $O(V)$입니다.

4) BFS의 특징

• BFS는 시작 노드(node)에서 가장 가까운 노드(node)를 먼저 방문하므로, 최단 경로(path)를 찾는 문제에 적합합니다.
• BFS는 큐를 사용하기 때문에, DFS보다 메모리를 더 많이 사용합니다.
• BFS는 무한 루프에 빠질 가능성이 없으므로, 안정적인 탐색을 보장합니다.

4. DFS와 BFS 비교

5. DFS와 BFS의 활용 사례

1) DFS 활용 사례

• 그래프의 모든 노드(node)를 방문해야 하는 경우
• 해(solution)가 깊숙한 곳에 있는 경우
• 사이클(cycle) 탐지
• 위상 정렬(topological sort)

2) BFS 활용 사례

• 최단 경로(path)를 찾는 경우 (예: 미로 탐색, 최단 경로(path) 찾기)
• 두 노드(node) 사이의 최소 거리(distance)를 구하는 경우
• 레벨별 탐색이 필요한 경우 (예: 소셜 네트워크에서 친구 관계 탐색)
• 이분 그래프(bipartite graph) 판별

6. 결론

DFS와 BFS는 그래프 탐색의 기본적인 알고리즘이며, 각각의 장단점을 이해하고 문제의 특성에 맞게 적절한 알고리즘을 선택하는 것이 중요합니다. DFS는 깊이 우선 탐색으로, 스택 또는 재귀 호출을 사용하여 구현하며, 모든 노드(node)를 방문하거나 해(solution)가 깊숙한 곳에 있는 문제에 적합합니다. BFS는 너비 우선 탐색으로, 큐를 사용하여 구현하며, 최단 경로(path)를 찾는 문제에 적합합니다. 두 알고리즘 모두 시간 복잡도와 공간 복잡도를 고려하여 선택해야 하며, 문제 해결에 효율적인 알고리즘을 선택하기 위해서는 다양한 문제를 풀어보며 경험을 쌓는 것이 중요합니다.