1. 문제 링크
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
2. 문제 설명
N을 입력받아 크기가 N * N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수를 출력하는 문제입니다.
퀸이 서로 공격할 수 없게 놓으려면 각각의 퀸이 다음 세 가지 조건을 모두 만족해야 합니다.
1. 한 행(row)에는 하나의 퀸만 있어야 한다.
2. 한 열(col)에는 하나의 퀸만 있어야 한다.
3. 대각선(diagonal)에는 하나의 퀸만 있어야 한다.
| (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) |
N이 4일 때 퀸을 놓을 수 있는 방법 중 하나입니다.
1번 조건은 for문을 돌면서 한 행에 하나의 퀸만 놓아보면 되므로 생각하지 않아도 됩니다.
2번 조건은 현재 퀸이 놓여있는 열의 위치를 저장해놓는 bool check_col[15]배열을 만들고,
퀸이 있으면 true, 없으면 false로 표현해서 퀸을 놓기 전에 해당 열에 퀸이 있는지 확인해보면 됩니다.
3번 조건은 북동쪽 방향 대각선(왼쪽 아래에서 오른쪽 위)와, 남동쪽 방향 대각선(왼쪽 위에서 오른쪽 아래)을 모두 확인해봐야 합니다.
먼저, 같은 북동 대각선에 있는 경우 row + col의 값이 같은 것을 알 수 있습니다.
이 값의 범위는 0 ~ 2 * (N - 1)이므로 현재 퀸이 놓여있는 북동 대각선의 위치를 저장해놓는 bool check_diag_ne[30]배열을 만들고,
퀸이 있으면 true, 없으면 false로 표현해서 퀸을 놓기 전에 해당 북동 대각선에 퀸이 있는지 확인해보면 됩니다.
다음으로, 같은 남동쪽 방향 대각선(왼쪽 위에서 오른쪽 아래)에 있는 경우 row - col의 값이 같은 것을 알 수 있습니다.
이 값의 범위는 -(N - 1) ~ (N - 1)인데, 배열의 인덱스로 사용하기 위해 N을 더해주면 1 ~ (2 * N) - 1이므로
현재 퀸이 놓여있는 남동 대각선의 위치를 저장해놓는 bool check_diag_se[30]배열을 만들고,
퀸이 있으면 true, 없으면 false로 표현해서 퀸을 놓기 전에 해당 남동 대각선에 퀸이 있는지 확인해보면 됩니다.
3. 소스코드
BOJ 9663번 N-Queen C++ 풀이입니다.
#include <iostream>
using namespace std;
int N, cnt;
bool check_col[15];
bool check_diag_ne[30];
bool check_diag_se[30];
void nqueen(int row)
{
if (row == N) {
cnt++;
return;
}
for (int col = 0; col < N; col++) {
if (check_col[col] || check_diag_ne[row + col] || check_diag_se[row - col + N])
continue;
check_col[col] = true;
check_diag_ne[row + col] = true;
check_diag_se[row - col + N] = true;
nqueen(row + 1);
check_col[col] = false;
check_diag_ne[row + col] = false;
check_diag_se[row - col + N] = false;
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
nqueen(0);
cout << cnt;
return 0;
}
4번 라인 : N을 입력받을 int N과, 최종 정답을 출력할 int cnt를 선언합니다.
5번 라인 : 현재 퀸이 놓여있는 열을 체크하기 위해서 bool check_col[15]를 선언합니다.
6번 라인 : 현재 퀸이 놓여있는 북동쪽 방향 대각선(왼쪽 아래에서 오른쪽 위)을 체크하기 위해서 check_diag_ne[30]을 선언합니다.
7번 라인 : 현재 퀸이 놓여있는 남동쪽 방향 대각선(왼쪽 위에서 오른쪽 아래)을 체크하기 위해서 check_diag_se[30]을 선언합니다.
36번 라인 : 0번째 row부터 퀸을 놓아보기 위해서 nqueen(0)을 호출합니다.
11번 라인 : row가 N이면 퀸을 마지막 행까지 놓을 수 있는 것이기 때문에 cnt를 1 증가시키고 return 시킵니다.
16번 라인 : 현재 행의 몇번째 열에 퀸을 놓을지 결정하기 위해 0부터 N - 1까지 for문을 돌립니다.
17, 18번 라인 : 같은 열에 이미 퀸이 있거나(check_col[col] == true), 북동쪽 방향 대각선에 퀸이 있거나(check_diag_ne[row + col] == true), 남동쪽 방향 대각선에 퀸이 있으면(check_diag_se[row - col + N]) 현재 열에는 퀸을 놓을 수 없으므로 다음 열에 퀸을 놓아보기 위해서 continue합니다.
19, 20, 21번 라인 : 17번 라인 if조건의 값이 모두 false이면 현재 열에는 퀸을 놓을 수 있으므로, 퀸을 놓았다는 표시로 check_col[col], check_diag_ne[row + col], check_diag_se[row - col + N] 에 true를 대입합니다.
22번 라인 : 현재 행에 퀸을 놓았으므로 다음 행에 퀸을 놓아보기 위해 nqueen(row + 1)을 호출합니다.
23, 24, 25번 라인 : 23번 라인이 실행될 때는 현재 열에 퀸을 놓았을 때의 경우의 수를 모두 실행해본 후 돌아온 것이기 때문에 현재 열에 퀸을 놓지 않았을 때의 경우의 수를 확인해보기 위해서 퀸을 놓지 않았다는 표시로 check_col[col], check_diag_ne[row + col], check_diag_se[row - col + N] 에 false를 대입합니다.
37번 라인 : 재귀가 끝났으므로 최종 결과를 출력합니다.
'Algorithm' 카테고리의 다른 글
| [백준 2579번 C++] 계단 오르기 (0) | 2020.11.09 |
|---|---|
| [백준 2580번 C++] 스도쿠 (0) | 2020.10.13 |
| [백준 14888번 C++] 연산자 끼워넣기 (0) | 2020.10.07 |
| [백준 11399번 C++] ATM (0) | 2020.10.05 |
| [백준 2309번 C++] 일곱 난쟁이 (0) | 2020.10.05 |
