[Leetcode] 51. N-Queens

문제 : https://leetcode.com/problems/n-queens/

---

두 개의 퀸이 서로 공격하지 않도록 n x n 체스판에 n개의 퀸을 배치하라.

가능한 모든 경우의 체스판 형태를 반환하라. (Q : 퀸, . : 빈칸)

(참고로 퀸은 한 번 움직일 때 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동 가능)

---

백트래킹으로 풀었다.

퀸은 앞, 뒤, 옆, 대각선 방향을 원하는 만큼 이동 가능하기 때문에 row, col, 대각선에 놓을 수 있는지 여부를 저장해야 한다.

백트래킹 구현 시 하나의 행에 퀸을 두는 경우의 수를 판단한다고 하면 하나의 행에는 하나의 퀸만 놓게 구현하면 row 에 퀸을 놓을 수 있는지 여부는 저장을 하지 않아도 된다.

열의 퀸 저장가능 여부는 n 크기의 boolean 배열로 해결 가능하다.

 

x + k = y   ->  k = -x + y
-x + k = y  ->  k = x + y

문제는 대각선인데, 배열에서 대각선은 기울기가 1이나 -1인 일차방정식과 같다고 생각하면 수식을 유추하기 쉽다.

위 수식으로 k가 동일하면 같은 대각선이라고 판단할 수 있다.

N = 4

N이 4인 경우 수식을 대입하면 위와 같은 그림이 된다.

같은 값을 가지는 곳들이 같은 대각선 상에 있다고 볼 수 있다.

값의 범위는 -3 ~ 3, 0 ~ 6이 나온다.

인덱스가 음수면 배열 인덱스로 사용할 수 없으므로 3을 더해줘서 모두 0이상의 값으로 만들어준다.

이것으로 값의 범위는 행 - 열, 열 - 행 모두 0 ~ 6이 되어, 해당 크기의 배열을 만들어서 퀸의 세팅가능여부를 판단할 수 있다.

 

백트래킹으로 가능한 배열을 만들어나가면서 N개의 퀸을 채운 경우 정답 배열에 추가해준다.

 

시간복잡도는 O(N!)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/51.%20N-Queens.cpp