[알고리즘] DFS와 BFS 이해하기

1. DFS(깊이 우선 탐색)

• 시작 노드에서 한 경로를 최대한 깊이 탐색한 후, 더 이상 탐색할 수 없을 때 되돌아와 다른 경로를 탐색한다.
• 스택(Stack) 또는 재귀를 사용하여 구현할 수 있다.
• 일반적으로 그래프나 트리에서 깊이 방향으로 탐색한다.
• 깊이를 우선으로 탐색하기 때문에 어떤 경로에서 더 이상 탐색할 수 없을 때까지 깊이 탐색한다.

2. BFS(너비 우선 탐색)

• 시작 노드에서 인접한 모든 노드를 먼저 탐색한 후, 다음 레벨의 노드로 이동하여 탐색한다.
• 큐(Queue)를 사용하여 구현할 수 있다.
• 일반적으로 그래프나 트리에서 너비 방향으로 탐색한다.
• 가까운 노드부터 탐색하기 때문에 최단 경로나 최단 거리를 찾는 데 유용한다.

예시

   A
 / | \
B  C  D
|     |
E     F

DFS (깊이 우선 탐색)

1. A에서 시작한다. A를 방문했다고 표시한다.
2. A의 인접한 노드 중에서 방문하지 않은 B를 선택하여 B로 이동한다. B를 방문했다고 표시한다.
3. B의 인접한 노드 중에서 방문하지 않은 E를 선택하여 E로 이동한다. E를 방문했다고 표시한다.
4. E의 인접한 노드가 없으므로 이전 단계로 돌아가 B의 다른 인접 노드를 확인한다. 방문하지 않은 C를 선택하여 C로 이동한다. C를 방문했다고 표시한다.
5. C의 인접한 노드가 없으므로 이전 단계로 돌아가 A의 다른 인접 노드를 확인한다. 방문하지 않은 D를 선택하여 D로 이동한다. D를 방문했다고 표시한다.
6. D의 인접한 노드 중에서 방문하지 않은 F를 선택하여 F로 이동한다. F를 방문했다고 표시한다.
7. F의 인접한 노드가 없으므로 이전 단계로 돌아가 D의 다른 인접 노드를 확인한다. D의 모든 인접 노드를 방문했으므로 이전 단계로 돌아가 A의 다른 인접 노드를 확인한다.
8. 모든 노드를 방문 완료

   A
 / | \
B  C  D
|     |
E     F

BFS (너비 우선 탐색)

1. A에서 시작한다. A를 방문했다고 표시한다.
2. A의 인접한 노드인 B, C, D를 큐에 넣는다.
3. 큐에서 첫 번째로 들어온 노드인 B를 선택하여 B를 방문했다고 표시한다.
4. B의 인접한 노드인 E를 큐에 넣는다.
5. 큐에서 두 번째로 들어온 노드인 C를 선택하여 C를 방문했다고 표시한다.
6. C의 인접한 노드는 없으므로 넘어간다.
7. 큐에서 세 번째로 들어온 노드인 D를 선택하여 D를 방문했다고 표시한다.
8. D의 인접한 노드인 F를 큐에 넣는다.
9. 큐에서 네 번째로 들어온 노드인 E를 선택하여 E를 방문했다고 표시한다.
10. E의 인접한 노드는 없으므로 넘어간다.
11. 큐에서 다섯 번째로 들어온 노드인 F를 선택하여 F를 방문했다고 표시한다.
12. F의 인접한 노드는 없으므로 넘어간다.
13. 모든 노드를 방문 완료

시간 복잡도

DFS (깊이 우선 탐색)

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

여기서 V는 노드(정점)의 수이고, E는 간선의 수이다. DFS는 스택(Stack) 또는 재귀 호출을 사용하여 구현된다. 각 노드를 최대 한 번 방문하며, 각 간선은 정확히 한 번만 검사된다. 따라서 시간 복잡도는 노드와 간선의 수에 비례한다. 공간 복잡도는 DFS 호출 시 사용되는 스택의 깊이에 비례하므로 O(V)이다.

BFS (너비 우선 탐색)

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

BFS는 큐(Queue)를 사용하여 구현된다. 각 노드를 한 번 방문하고, 각 간선은 정확히 한 번만 검사된다. 따라서 시간 복잡도는 노드와 간선의 수에 비례한다. 공간 복잡도는 BFS에서 사용되는 큐의 크기에 비례하므로 O(V)이다.

따라서 일반적으로 DFS와 BFS의 시간 복잡도와 공간 복잡도는 동일하며, 그래프의 크기에 따라 선형적으로 증가한다. 그러나 특정한 상황에서는 각각의 알고리즘의 특성에 따라 성능이 달라질 수 있다.