BFS
BFS는 그래프나 트리에서 최단 경로를 찾을 때 or 모든 경로를 동일한 깊이로 탐색할 때 유용하다.
큐를 이용하여 현재 노드와 연결된 모든 이웃을 한 번에 탐색하고, 그 다음 이웃의 이웃을 탐색하는 방식으로 작동한다.
BFS가 최적인 경우
-
가중치가 없는 그래프에서의 최단 경로
BFS는 그래프에서 간선의 가중치가 모두 동일할 때 출발점에서 도착점까지의 최단 경로를 보장한다.
즉, BFS는 한 번 방문한 위치는 그 위치에 도달하는 가장 짧은 시간을 이미 계산하고 지나가기 때문에, 이후에는 그 위치에 다시 도달할 때 더 나은 시간이 될 수 없다. 한 번 방문한 노드에 대해 더 짧은 경로가 없다는 것이 BFS의 특성이다.
간선의 가중치가 없거나 같을 때 BFS는 가장 먼저 방문하는 경로가 최단 경로임을 보장한다.
ex) 미로 탐색 문제(벽을 제외하고 1칸씩 이동하는 최단 경로 찾는 문제) -
가중치가 없는 그래프에서의 최소 비용 경로
가중치가 없는 그래프에서 출발점에서 도착점까지 최소 비용으로 이동할 수 있는 경로를 찾을 때 적합하다. -
최소 레벨 탐색
트리나 그래프에서 최소 레벨의 노드를 찾을 때 효율적이다.
트리 구조에서 BFS는 루트에서부터 시작하여 레벨별로 노드를 탐색한다.
BFS가 비효율적인 경우
그래프의 크기나 너무 클 때, 메모리 소모가 크다.
너비 우선으로 탐색하므로 탐색 공간이 넓어질 수록 많은 노드를 메모리에 저장해야 한다.
DFS
DFS는 스택이나 재귀를 사용해서 경로를 깊게 탐색한다.
DFS는 모든 경로를 탐색한 후에 돌아와 다른 경로를 탐색하므로, 목적지가 깊이 있는 곳에 있을 때 유리하다.
DFS가 최적인 경우
-
모든 경로 탐색
DFS는 모든 경로를 끝까지 탐색한 후에 돌아오므로, 모든 가능한 경로를 탐색해야 하는 문제에서 유용하다.
예를 들어, 가능한 모든 경로를 찾아야 하거나 최악의 경우까지 탐색이 필요할 때가 있다.
ex) 백트래킹, 미로의 모든 경로 탐색, 모든 가능한 조합이나 순열을 찾는 문제 -
사이클 탐지
방문한 노드를 기록한 뒤, 다시 그 노드를 방문하면 사이클이 존재함을 알 수 있다. -
재귀적 구조를 가진 문제
트리 탐색이나 재귀적으로 문제를 풀 때 적합하다.
ex. 트리의 최대 깊이 찾기, 분할 정복 문제
DFS가 비효율적인 경우
최단 경로를 찾을 때 비효율적일 수 있다.
경로를 깊이 탐색하지만, 먼저 탐색한 경로가 최적이 아닐 가능성이 높기 때문에 최단 경로를 보장하지 않는다.
Dijkkstra
다익스트라 알고리즘은 가중치가 있는 그래프에서 출발점에서 모든 노드까지의 최단 경로를 찾는 알고리즘이다.
우선순위 큐를 사용해 현재까지 가장 짧은 경로로 방문할 수 있는 노드를 선택하여 계속 탐색하는 방식이다.
모든 간선의 가중치가 0 또는 양수일 때만 사용할 수 있다.
Dijkstra가 최적인 경우
-
양의 가중치 그래프에서 최단경로를 찾을 때
가중치가 양수인 그래프에서 출발점에서 다른 모든 노드까지의 최단 경로를 찾는 문제에 적합하다.
ex. 도로 네트워크 문제, 배달 문제, 네비게이션 경로 탐색 문제 -
여러 경로 중 가장 짧은 경로를 찾을 때
여러 경로 중에서 가중치의 합이 가장 작은 경로를 찾아야 하는 문제에서 다익스트라가 최적이다.
ex. 출발점에서 목표지점까지 가장 적은 비용으로 이동하는 경로
Dijkkstra가 비효율적인 경우
-
음의 가중치가 있는 경우
음의 가중치가 있을 때는 올바를 답을 보장하지 못한다.
음의 가중치가 있는 경우에는 벨만-포드 알고리즘을 사용해야 한다. -
특정 노드에서 특정 노드까지의 경로만 구할 때
만약 출발점에서 특정 노드까지만 최단 경로를 구하고 싶다면 다익스트라 알고리즘은 모든 노드를 탐색하기 때문에 비효율적이다.
요약
- BFS
- 최적의 경우: 가중치 없는 그래프에서 최단 경로를 찾을 때, 최소 레벨 탐색을 할 때.
- 비효율적인 경우: 그래프의 크기가 너무 크거나 깊이 있는 경로를 탐색할 때.
- DFS
- 최적의 경우: 모든 경로를 탐색해야 하거나, 재귀적 구조, 백트래킹, 사이클 탐지 문제에서 유리.
- 비효율적인 경우: 최단 경로를 찾는 문제에서 비효율적일 수 있음.
- Dijkkstra
- 최적의 경우: 가중치가 있는 양의 가중치 그래프에서 최단 경로를 찾을 때.
- 비효율적인 경우: 음의 가중치가 있는 그래프에서는 사용할 수 없으며, 특정 경로만 구할 때 모든 경로를 탐색해야 하므로 비효율적일 수 있음.
