백준 9663 - N-Queen

🔐 백준 9663 - N-Queen

https://www.acmicpc.net/problem/9663

🔑 풀이

처음 문제에 접근했을 때, $ N \times N $ 크기의 체스판 위에 퀸 N개를 놓아야 된다는 것을 보고

$ N \times N $ 의 (0, 0) 좌표부터 백트래킹을 통해 모든 경우의 수를 계산하는 방식으로 풀어야겠다고

생각했다. DFS 를 이용해서 좌표의 네 방향으로 뻗어나가며 퀸을 놓을 수 있는지 없는지를 판단하고

가지치기를 진행해야겠다고 생각했지만, 퀸의 특성 상, 동일한 x, y 좌표에는 다른 퀸을 놓을 수가 없기

때문에, 굉장히 비효율적인 방법임을 깨달았다.

우선, 퀸은 같은 x, y좌표와 대각선으로 이동할 수 있다. x, y 좌표의 경우 조사하려는 x, y 좌표와

같은지만 조사하면 되기 때문에 쉽게 해결할 수 있지만, 대각선의 경우 코드로 어떻게 표현해야 할지 몰랐다.

2차원 배열에서 대각선은 다음과 같은 특성을 가지고 있었다.

위 두 특성을 조합하면 $ \vert row1 - row2 \vert = \vert col1 - col2 \vert $ 가 되며, 쉽게 코드로 나타낼 수 있다.

$ 4 \times 4 $ 크기의 체스판에 4개의 퀸을 놓는 경우를 예시로 들어보면, 우선 (0, 0)에 퀸을 놓은 경우

0행의 다른 칸은 생각할 필요가 없다. 따라서 2차원 배열을 만들 필요가 없으며, 1차원 배열로도 문제를

해결할 수 있다. 이제 1행에 퀸을 놓을 수 있는지를 확인하고, (1, 2), (1, 3)에 놓을 수 있으므로, 각각에

대해 실행시켜 줄 것이다. 이러한 방식으로 코드를 짜주면 해결할 수 있다.

🧩 코드

• isSafe() 함수를 사용하여 반복문을 통해 열과 대각선을 체크하는 것은 연산 횟수를 많이 쓰게 됨.

• 따라서 열과 대각선 2개에 대한 배열을 통해 같은 열과 대각선 상에 퀸이 존재하는 지를 체크하는 방법을
  사용하면 시간을 단축시킬 수 있음.