[백준 9663] N-Queen [C]

백준 - 9663

---

풀이

하나의 행에는 하나의 퀸만 존재한다는 점을 이용해, 배열의 index는 행, value는 퀸의 위치로 구현했다.

 

nQueen()

• 0행 부터 Brute Force 방식으로 퀸이 놓일 수 있는지 확인하고, cnt값을 조작한다.

put_check()

• 현재 행(index)의 value(퀸의 위치)가 다음 행의 value와 일치한다면, 동일한 열에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다.
• 현재 행(row)에서 이전 행(i)들을 뺀 값이 현재 행의 value(퀸의 위치)에서 이전 행의 value를 뺀 절대값과 동일하다면, 동일한 대각선 상에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다.

---

소스코드

#include <stdio.h>
#include <math.h>
int N, board[15], cnt;
int put_check(int row){
    for (int i = 0; i < row; i++)
        if (board[row] == board[i] || row - i == abs(board[row] - board[i]))
            return 0;
    return 1;
}
void nQueen(int row) {
    if(row == N)
        cnt++;
	else
        for (int Q = 0; Q < N; Q++){
            board[row] = Q;
            if (put_check(row))
                nQueen(row + 1);
        }
}
int main() {
    scanf("%d", &N);
    nQueen(0);
    printf("%d", cnt);
}

---

출처

9663번: N-Queen