DFS / BFS

DFS(Depth-First Search)

깊이를 우선하여 탐색하는 방법으로 하나의 경로를 끝까지 탐색한 후, 돌아와서 다른 경로를 탐색한다.

스택(Stack)이나 재귀 함수를 사용하여 구현할 수 있다.

 

장점

1. 구현이 비교적 간단하다 (스택, 재귀 함수를 사용하여 구현)
2. 메모리 사용량이 적다. DFS는 스택을 사용하여 탐색 경로를 저장하므로, 메모리 적은 편이다. (탐색 경로에 대한 정보만 필요)
3. 최단 경로를 찾을 때 유용하다. 탐색 중에 목표 지점에 도달하면 탐색을 종료할 수 있기 때문

단점

1. 무한 루프의 위험성 :  그래프에 순환 경로가 있는 경우, DFS는 순환 경로를 계속해서 탐색하여 무한 루프에 빠질 수 있다.
2. 최단 경로가 아닐 수 있다 : DFS는 깊이 우선으로 탐색하므로, 첫 번째로 발견한 해답이 최단 경로가 아닐 수도 있다.
3. 탐색 시간이 길 수 있다 : 그래프가 깊거나 가지가 많은 경우, DFS는 탐색 시간이 길어질 수 있다.

BFS(Breadth-First Search)

너비를 우선하여 탐색하는 방법으로 한 단계씩 진행하면서 해당 단계의 모든 노드를 탐색한다.

큐(Queue)를 사용하여 구현할 수 있다.

 

장점

1. 최단 경로를 찾을 수 있다 : 너비를 우선으로 탐색하므로, 시작점에서 가까운 노드부터 탐색하여 최단 경로를 찾을 수 있다.
2. 구현이 비교적 간단하다. (큐(Queue)를 사용하여 구현)
3. 한 단계씩 진행하면서 모든 이웃 노드를 탐색한 후에야 다음 단계로 진행한다. 단계별 정보를 활용하여 문제를 해결할 수 있다.

단점

1. 메모리 사용량이 크게 증가할 수 있다 : BFS는 모든 이웃 노드를 큐에 저장해야 하므로, 탐색하는 그래프의 크기가 커질수록 큐의 크기도 커지고 메모리 사용량이 증가할 수 있다.
2. 그래프가 깊거나 가지가 많은 경우 계산 시간이 길어질 수 있다.
3. 그래프의 순환 구조에서 무한 루프에 빠질 수 있다.