[JAVA] BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)

DFS(Depth-First Search, 깊이 우선 탐색)와 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리 구조에서 탐색하는 두 가지 대표적인 알고리즘으로, 탐색 방식에 뚜렷한 차이가 있어 사용되는 상황 또한 다르다. 각 알고리즘의 특징과 장단점을 살펴볼까요?

DFS (깊이 우선 탐색)

• 탐색 방식: 탐색할 수 있는 만큼 깊이 우선으로 탐색한다. 현재 노드에서 갈 수 있는 다음 노드가 있다면 그 노드를 방문하고, 더 이상 갈 곳이 없다면 이전 노드로 돌아가 다른 경로를 탐색, 마치 미로에서 한쪽 길을 끝까지 따라가다가 막히면 되돌아 나오는 방식과 유사하다.
• 구현 방식: 주로 재귀 함수나 스택 자료구조를 이용하여 구현.

장점:

• 구현이 비교적 간단할 수 있다 (특히 재귀 함수를 이용할 경우).
• 해결 경로가 깊이 숨겨져 있는 경우 BFS보다 빠르게 해답을 찾을 수 있다.
• 메모리 사용량이 BFS보다 적을 수 있다. 탐색 경로만 저장하면 되기 때문이다.

단점:

• 최단 경로를 보장하지 않는다. 깊이 우선으로 탐색하기 때문에, 찾은 해답이 최단 경로가 아닐 수 있다.
• 탐색 깊이가 무한한 그래프에 빠질 수 있다. 방문 처리를 제대로 하지 않으면 무한 루프에 빠질 위험이 있다.

사용처:

• 경로 존재 여부 확인: 특정 노드까지 도달할 수 있는지 확인하는 경우 유용하다.
• 모든 경우의 수 탐색: 순열, 조합과 같이 모든 가능한 경우의 수를 탐색해야 할 때 활용된다.
• 백트래킹: 해를 찾는 과정에서 막히면 이전 단계로 돌아가 다른 가능성을 탐색하는 백트래킹 알고리즘의 기반.
• 트리 구조 탐색: 트리 구조에서 특정 조건을 만족하는 노드를 찾거나 모든 노드를 순회하는 데 사용된다.

BFS (너비 우선 탐색)

• 탐색 방식: 시작 노드에서 가까운 노드부터 차례대로 탐색한다. 현재 노드와 연결된 모든 이웃 노드를 먼저 방문하고, 그 이웃 노드들의 이웃 노드를 방문하는 방식. 마치 물이 퍼져나가듯이 넓게 탐색.
• 구현 방식: 주로 큐 자료구조를 이용하여 구현.

장점:

• 최단 경로를 보장한다. 시작 노드에서 가장 가까운 노드부터 탐색하므로, 해답이 존재한다면 항상 최단 경로를 찾는다.
• 탐색 깊이가 제한된 경우에 효율적이다. 특정 깊이 이내의 노드만 탐색하면 되는 경우에 유용하다.

단점:

• DFS에 비해 구현이 복잡할 수 있다.
• 해결 경로가 깊거나 그래프의 크기가 매우 큰 경우 메모리 사용량이 많아질 수 있다. 탐색해야 할 노드들을 큐에 저장해야 하기 때문이다.

사용처:

• 최단 경로 찾기: 길 찾기, 네트워크 라우팅 등 최단 거리를 찾는 문제에 효과적이다.
• 레벨 기반 탐색: 트리 구조에서 특정 레벨의 노드들을 순회하거나, 각 노드의 깊이를 파악하는 데 사용된다.
• 모델링: 현실 세계의 연결 관계를 모델링하고 탐색하는 데 활용될 수 있다 (예: 소셜 네트워크 분석).

요약

• DFS는 깊이 있는 탐색에 유리하며, 모든 경우의 수를 탐색하거나 경로 존재 여부를 확인할 때, 그리고 메모리 사용량을 줄여야 할 때 주로 사용된다. 하지만 최단 경로를 보장하지 않고 무한 루프에 빠질 위험이 있다.
• BFS는 최단 경로를 찾는 데 강점을 가지며, 레벨 기반 탐색이나 넓은 범위의 탐색이 필요한 경우에 사용된다. 하지만 구현이 복잡할 수 있고, 메모리 사용량이 많아질 수 있다.