DFS (Depth-First-Search)
깊이 우선 탐색
-
그래프에서 노드를 탐색할 때 노드의 우선 순위에 따라 최대한 깊이 들어가 모든 노드를 방문하는 걸 목표로 한다. 깊이를 우선하다 보니 찾는 노드가 깊숙히 있을 때 유용하다.
-
예를 들면 어떤 게임의 전략을 찾을 때 하나의 경우의 수에 따른 모든 결과들을 파고들어 찾아낼 때 사용할 수 있다.
BFS (Bradth-First-Search)
너비 우선 탐색
-
큐를 활용하여 계층(깊이)별로 탐색하는 방법이다. 같은 깊이에 있는 노드들을 큐에 넣고 차례대로 꺼내 확인하며 순환하는 방식이다.
-
주로 최단경로 찾기, 인접한 노드 찾기 등에 사용된다. 깊이 들어가면 들어갈 수록 메모리 낭비가 심라기 때문에 노드가 많고 트리가 넓을 때 사용하면 비효율적이다.
백트래킹(Backtracking)
해결책을 찾는 과정에서 답이 될 가능성이 없는 경로인 경우 단어 그대로 뒤로 되돌아가서(back) 다른 경로를 따라가는(tracking) 알고리즘 기법이다.
주로 문제 풀이에서는 DFS등을 활용해 모든 경우의 수를 탐색하는 과정에서 해답이 나오지 않을 경로는 if문 등을 활용해 차단하고 가능성이 있는 경로만을 탐색하며 답을 찾게 된다.
