[백준 9663] N-Queen

[ 백준 9663 : N-Queen ]

N퀸문제는 너무나도 유명한 문제라서 인터넷에도 엄청나게 많이 풀이법들이 있다.
가장 직관적이고 그나마 접근하기 쉽게 풀었는데

만약 이 문제를 한번에 풀이법을 생각하지 못한다면 이것만 알면된다.
퀸은 모든 방향으로 공격이 가능하니 한 행 또는 한 열에 퀸은 무조건 한 개씩만 존재한다.
이것만 이용하면 쉽게 풀린다.

일단 퀸은 대각선과 가로세로에 모두 공격할 수 있다. 그러므로 한 좌표에 퀸이 놓아진다면 해당 행과 열에는 절대 퀸을 놓을 수 없다.
따라서 한 행에 한개씩 놓고 그다음 행에 0~N열까지 한번씩 놔보는 식으로 구현이가능하다.

N이 15 미만이기 때문에 최악의 경우 14(행)*14(열)충분히 10초이내에 들 수 있다.

나는 백트래킹을 통해 사실 그냥 완탐이지만 주어진 맵을 다시 그 전 상태로 돌리기를 위해 재귀를 이용했다.
해당 좌표에 퀸을 놓을 수 있는지를 알아보는 방법으로는 INT형 이차원 배열을 이용했는데
한 곳에 퀸을 놓고 그 퀸이 공격할 수 있는 모든 좌표에 +1씩해준다. 그 전상태로 돌아갈때는 -1을 해주는데
이 이유로는 총 두개의 퀸이 같은 좌표를 공격할 수 있다고 했을때 어떤 하나의 퀸이 없는 상태가 되더라도 해당 좌표에 퀸을 놓지 못하게 하기 위해서이다.