BackTracking with 9663번: N-Queen

백트래킹이란?

---

 백트래킹이란 원하는 값을 찾는 도중 현재 대상이 원하는 값이 아닐때, 더 이상 그 대상을 탐색하지 않고 전 단계로 돌아가서 원하는 값을 푸는 방식이다. 우리가 가장 많이 사용하는 방식인 DFS, BFS가 바로 백트래킹에 속한다고 한다. 

 

DFS, BFS가 바로 백트래킹에 속한다고 한다. 

 

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

 

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

 

백준 9663번: N-Queen

---

9663번: N-Queen - Kotlin (백트래킹)

 

 

 

이런 백트래킹 방식을 이용한 것들로는 순열과 조합이 있다.

순열 (Permutation) & 조합 (Combination)

 

 알고리즘 문제들을 점점 풀어가면서 느끼는 점은 하나만 알아서는 절대 많은 문제를 해결하지 못한다는 것이다. 알고리즘은 서로서로 연결되어 있고 서로를 변형하거나 발전시킨 방식임으로 한 방식만을 추구하지 말고 최대한 여러가지 방식을 전부 배워서 잘 응용한다면 많은 알고리즘 문제들을 해결할 수 있을 것이다.