[ 알고리즘 ] 백트래킹 (Backtracking)

백트래킹 이란?

재귀적으로 문제를 해결하는 기법으로, 가능한 모든 해를 탐색하면서 불가능한 해를 만났을 때는 되돌아가서 다른 경로를 탐색하는 방식.

 

 

백트래킹 단계

백트래킹의 구조는 기본적으로 DFS(깊이 우선 탐색)를 기반으로 하되, 조건문을 사용하여 불가능한 경로를 조기에 포기하는 방식이며 이를 통해 불필요한 탐색을 줄이고 효율적으로 해를 찾는다.

1. 해 탐색: 현재 경로를 확장하여 해를 탐색한다.
2. 유효성 검사: 현재 경로가 유효한지 검사 후 유효하지 않으면 그 경로를 포기하고 돌아간다.
3. 완전성 검사: 현재 경로가 완전한 해인지 검사한다. 완전한 해라면 결과를 기록한다.
4. 백트래킹: 위 단계들을 반복하며, 모든 가능성을 탐색한다.

 

 

백트래킹 사용

백트래킹은 퍼즐 문제(예: 미로 찾기, N-퀸 문제), 제약 만족 문제, 조합 최적화 문제 등에 많이 사용된다. 이를 통해 불필요한 경로를 일찍 포기함으로써 효율적으로 해를 찾을 수 있다.

 

 

 

백트래킹 vs DFS

	백트래킹	DFS
목적	그래프나 트리의 모든 노드를 방문하기 위해 사용	문제의 해를 찾기 위해 사용되며, 해를 찾지 못하면 돌아가 다른 경로를 탐색
탐색방법	모든 경로를 끝까지 탐색	불가능한 경로를 만날 경우 되돌아가서 다른 경로를 탐색
적용사례	그래프 탐색, 경로 찾기 등	퍼즐 풀이, 제약 만족 문제 등
효율	불필요한 경로까지 모두 탐색하므로 비효율적 일 수 있음	불가능한 경로를 일찍 포기하므로 효율적

 

 

 

▶ DFS

https://glenn-dev.tistory.com/15

[ 알고리즘 ] 깊이 우선 탐색 (DFS)