백준 9663번: N-Queen C++ Code

 백트레킹의 중심 아이디어는 재귀의 깊이를 명시적으로 설정한다는 것에 있다. 다만 n-queen문제와 같이 응용된 문제의 경우에는 무엇을 깊이로 할지 설정 해야하는 어려움이 있다. 물론 n-queen 문제의 풀이방식에는 여러가지가 있겠지만은 백트레킹으로 풀었다. 퀸을 두면서 check해야 되는 배열은 4가지가 있다. 종류로는 행, 열, 왼쪽 위 대각선, 오른쪽 위 대각선이 있다.

 

 이때 재귀의 깊이로 행 check를 하고, for반복문을 돌리면서 나머지 열, 왼쪽 위 대각선, 오른쪽 위 대각선에 대한 check를 수행했다. 나머지 수행은 기본 백트레킹 문제와 동일하기 때문에 생략하겠다.