BackTracking with 9663번: N-Queen

백트래킹이란? 백트래킹이란 원하는 값을 찾는 도중 현재 대상이 원하는 값이 아닐때, 더 이상 그 대상을 탐색하지 않고 전 단계로 돌아가서 원하는 값을 푸는 방식이다.

우리가 가장 많이 사용하는 방식인 DFS, BFS가 바로 백트래킹에 속한다고 한다. DFS, BFS가 바로 백트래킹에 속한다고 한다.

사실 이 말은 매우 불친절한 말이다. 백트래킹이 무엇인가에 대해 의문점이 생겨서 많은 게시글들을 참고하고 여기저기를 뒤져본 결과 나름 내가 내려본 결론은 백트래킹은 DFS 나 BFS에서 조건문을 통해 우리가 찾고자 하는 값이 절대 아닌 것들은 탐색하지 않고 우리가 찾고자 하는 값이 있는 것들만을 탐색하여 우리가 원하는 값을 찾는 방식이라고 생각한다.

이해를 돕기위한 예로 유명한 백트래킹 문제를 가져와 보겠다......