[Algorithm] Backtracking

🌳 Bactracking Algorithm

해를 찾는 도중, 해가 아니어서 막히면 다시 왔던 길로 되돌아가 다른 해를 찾아가는 기법

💡DFS(깊이 우선 탐색)에 기반한다. 깊이우선탐색은 가능한 모든 경로를 탐색하는데, 백트래킹은 해를 찾아가는 도중 지금의 경로가 해가 아니라면 되돌아간다.

(깊이우선방식뿐 아니라 너비우선방식도 사용될 수 있지만 모든 경우의 수를 고려하는 문제에서는 깊이우선방식이 더 낫다)

💡즉, 백트래킹은 가능한 모든 경우의 수를 탐색할 때, 특정 조건을 만족하는 경우만 살펴보는 것이다.

💡백트래킹은 가지치기(Prunning)을 통해 가능성 없는 루트를 가지치기 함으로써 효율을 극대화한다.

💡주로 '재귀'의 방식으로 구현된다.

관련 문제 https://www.acmicpc.net/problem/15649