DFS와 백트래킹

DFS(Depth-First Search, 깊이 우선 탐색)

• 그래프 탐색 알고리즘으로, 그래프의 노드들을 탐색하는 방법 중 하나

• 다른 그래프 탐색 알고리즘으로는 대표적으로 BFS(Breadth-First Search, 너비 우선 탐색)가 있다.

• DFS는 시작 노드에서 한 방향으로 가능한 멀리까지 탐색한 후, 더 이상 진행할 수 없을 때 다시 돌아와 다음 방향으로 탐색을 진행하는 방식

• 스택(Stack) 자료구조를 사용하여 구현되며, 가장 깊은 노드를 우선으로 탐색하는 특성을 가지고 있음

• 그래프에서 사이클을 찾거나, 특정한 경로를 찾는 문제, 백트래킹(backtracking) 등에 유용

백트래킹

• 백트래킹은 DFS 알고리즘의 한 변형으로 볼 수 있음

• DFS를 기반으로 하면서, 불필요한 경우를 미리 제외하여 탐색의 효율성을 향상시키는 방법

일반적으로 다음의 단계를 따름
1. 선택(Select): 다음에 어떤 선택을 할 것인지 결정
2. 제약(Constraint): 선택한 경우의 유망성을 평가합니다. 현재 상태에서 해를 찾기 위해 유망하지 않은 경우 해당 분기를 가지치기(pruning)
3. 결정(Decision): 선택한 경우를 해답에 추가하거나, 다음 선택으로 넘어간다.
4 .반복(Iterate): 모든 선택이 완료될 때까지 위 과정을 반복

• DFS는 백트래킹에서 "선택"과 "결정" 단계를 담당하며, 백트래킹은 "제약" 단계를 추가하여 불필요한 탐색을 제외하고 효율적으로 문제를 해결하는 것