BFS(Breadth-First Search)
[너비 우선 탐색]
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때
특징
- 직관적이지 않은 면이 있음.
- 재귀적으로 동작하지 않음.
- 알고리즘을 구현할 때, 그래프 탐색*의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함. 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있음.
- 대표적인 자료 구조: Queue
- 선입선출 구조
- 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작함.
*그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
DFS(Depth-First Search)
[깊이 우선 탐색]
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 사용하는 경우: 모든 노드를 방문하고자 하는 경우
특징
- 순환 알고리즘의 형태를 가짐.
- 전위 순회*를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류임.
- 알고리즘을 구현할 때, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함. 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있음.
*전위 순회(Pre-Order Traversals): Root → Left → Right
BFS VS DFS
1) BFS가 DFS보다 좀 더 복잡함.
2) DFS가 BFS에 비해 단순 검색 속도 자체가 더 느림.
EX) 지구상에 존재하는 모든 친구 고나계를 그래프로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
- BFS - A와 가까운 관계부터 탐색함.
- DFS - 모든 친구 관계를 다 살펴봄.
백트래킹(Backtracking)
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
최적화 문제와 결정 문제를 푸는 방법이 됨.
EX) 재귀 호출 or 스택을 통한 DFS
백트래킹 기법의 유망성 판단
- 유망하다(promising): 해가 될 가능성이 있는 것
- 가지치기(pruning): 유망하지 않은 노드에 가지 않는 것
원리
1) 노드의 유망성 점검
2) 유망하지 않을 경우 배제 = 가지치기
3) 해당 노드의 부모노드로 되돌아간 후 다른 자손노드 검색 → 풀이시간 단축
VS DFS(Depth-First Search)
DFS의 경우 가능한 모든 경로를 탐색하기 때문에 불필요할 것 같은 경로를 사전에 차단하는 등의 행동이 없어 경우의 수를 줄이지 못함.
백트래킹은 경우의 수를 줄일 수 있어 백트래킹이 이 부분에서는 더 효율적이라 할 수 있음.
이는 알고리즘을 작성할 때, 반복문의 횟수까지 줄일 수 있음.
N!과 같은 경우의 수가 많아지는 경우는 DFS로 처리가 불가능하지만 백트래킹은 가지치기를 어떻게 하냐에 따라 효율성이 결정되므로 처리가 가능할 수 있음.
- 백트래킹: 모든 가능한 경우의 수 중에서 특정한 조건을 만족한느 경우만 살펴보는 것.
- 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것.
- 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있음.
어떤 노드의 유망성, 즉 해가 될만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 감.
예제 문제
참고 자료
