링크
https://www.acmicpc.net/problem/9663
입력 예제
8출력 예제
92풀이
퀸은 가로, 세로, 대각선을 제한 없이 이동할 수 있다. 따라서 각 행에는 하나의 퀸만 존재할 수 있는데, 체스판의 크기가 4일 때를 생각해보면
Q (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)퀸을 (0, 0)에 놓는다면 다음 행에 놓을 수 있는 퀸은 (1, 2), (1, 3)이 된다.
Q (0,1) (0,2) (0,3)
(1,0) (1,1) Q (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)(1, 2)에 퀸을 놓는다면 더이상 퀸을 놓을 수 없어 다시 (1, 3)에 퀸을 놓는 경우로 올라간다.
Q (0,1) (0,2) (0,3)
(1,0) (1,1) (1,3) Q
(2,0) Q (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)그러면 다음 행에서 놓을 수 있는 경우는 (2, 1)가 되고 그 다음 행에서 놓을 수 있는 경우는 존재하지 않으니 다시 (0, 0)을 놓았던 경우로 올라간다.
이런식으로 첫번째 행의 각 열에 퀸을 놓으면서 재귀를 호출해나가며, 마지막 행까지 진행했다면 카운트하면 된다.
우선 해당 위치에 퀸을 놓을 수 있는지 여부를 알 수 있어야 한다. 해당 열에 퀸이 존재하는 지는 colCheck배열로 확인한다. (i, j)에 퀸을 놓으면 colCheck[j] = true가 된다.
기울기가 양수인 대각선의 경우는 plusDiagonalCheck배열로 확인하는데, 2차원 배열을 보면 같은 기울기의 좌표에서는 각 절편의 합과 같다. 가령 (2, 0), (1, 1), (0, 2)은 같은 대각선에 위치한다. 그래서 (i, j)에 퀸을 놓는다면 plusDiagonalCheck[i + j] = true가 된다.
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)기울기가 음수인 대각선의 경우는 각 좌표의 i - j 값이 동일하다. 가령 (1, 0), (0, 1)은 같은 기울기 상에 존재한다. 다만 음수가 될 수 있기 때문에 체스판의 크기에 - 1을 한 값을 더해준다. (i, j)에 퀸을 놓는다면 minusDiagonalCheck[i - j + N - 1] = true가 된다.
결국 재귀 함수는 다음과 같이 구현한다.
static void recur(int row) {
if (row == N) { //마지막 행까지 퀸을 놓은 경우
count++;
return;
}
for (int col = 0; col < N; col++) {
if (canPlaceQueen(row, col)) {
updateQueen(row, col, true); //퀸 배치
recur(row + 1);
updateQueen(row, col, false); //퀸 제거
}
}
}
//(row, col)에 퀸 배치 가능 여부 반환
private static boolean canPlaceQueen(int row, int col) {
return !colCheck[col] && //같은 열에 퀸 존재 여부
!plusDiagonalCheck[row + col] && //양의 기울기인 대각선에 퀸 존재 여부
!minusDiagonalCheck[row - col + N - 1]; //음의 기울기인 대각선에 퀸 존재 여부
}
//(row, col)에 퀸 배치 또는 제거
private static void updateQueen(int row, int col, boolean state) {
colCheck[col] = state;
plusDiagonalCheck[row + col] = state;
minusDiagonalCheck[row - col + N - 1] = state;
}전체 코드
//백준
public class Main {
static int N, count;
static boolean[] board;
static boolean[] colCheck = new boolean[14];
static boolean[] plusDiagonalCheck = new boolean[27];
static boolean[] minusDiagonalCheck = new boolean[27];
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
board = new boolean[N];
recur(0); //0번 행부터 시작
System.out.println(count);
}
static void recur(int row) {
if (row == N) { //마지막 행까지 퀸을 놓은 경우
count++;
return;
}
//모든 열에 대해 반복
for (int col = 0; col < N; col++) {
if (canPlaceQueen(row, col)) {
updateQueen(row, col, true); //퀸 배치
recur(row + 1);
updateQueen(row, col, false); //퀸 제거
}
}
}
//(row, col)에 퀸 배치 가능 여부 반환
private static boolean canPlaceQueen(int row, int col) {
return !colCheck[col] && //같은 열에 퀸 존재 여부
!plusDiagonalCheck[row + col] && //양의 기울기인 대각선에 퀸 존재 여부
!minusDiagonalCheck[row - col + N - 1]; //음의 기울기인 대각선에 퀸 존재 여부
}
//(row, col)에 퀸 배치 또는 제거
private static void updateQueen(int row, int col, boolean state) {
colCheck[col] = state;
plusDiagonalCheck[row + col] = state;
minusDiagonalCheck[row - col + N - 1] = state;
}
}