백준 온라인 저지의 9663번 N-Queen 문제입니다.
문제 조건과 설명
- N-Queen 문제란 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제입니다.
- 여기서 서로 공격할 수 없다는 조건은 다음과 같습니다.
- 퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다.
- 그림으로 살펴보면 다음과 같습니다.
Input
첫째 줄에 N이 주어집니다. (1 <= N < 15)
Output
퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력합니다.
생각한 아이디어
위 그림에서, 다음 행에 둘 수 없기 때문에 이전으로 되돌아가는 과정이 백트래킹입니다.
처음에 N*N 보드판에서의 일을 생각했기 때문에, 코딩할 때도 이차원 배열을 선언하려 했습니다.
작성한 뒤 여러 자료들을 참고해 다시 공부해 보니, 굳이 이차원 배열을 사용할 필요가 없었습니다.
위와 같이 생각할 수 있습니다. 즉, 놓인 퀸의 열 위치에 따라 (2,0,3,1) 로 읽을 수 있습니다.
이 열의 위치를 담는 1차원 배열만 만들어서 사용하면 코딩할 수 있습니다.
그 이유는 다음과 같습니다.
위 그림은 체스판에서 퀸의 열 위치가 같았을 때 입니다.
즉, 1차원 배열에서 값이 하나라도 같은 것이 있게 되면, 열 위치가 같다는 것이므로 넘어갈 수 있습니다.
위 그림은 0번째와 1번째 행에는 퀸을 놓았고, 그 다음 2번째 행에 퀸을 놓는 과정입니다.
2번째 행의 첫번째 열에 두었을 때에는 (1,0)과 열 위치가 같으므로 넘어갔을 것입니다.
그 다음 두번째 열에 두었을 때가 위 그림의 상황인데, (1,0)의 대각선상에 위치하게 됩니다.
대각선상에 위치한지 알아보는 방법은,
- 유망성을 판단할 위치인 (2,1)의 행 번호와, 그 위에 놓여 있는 다른 퀸들의 행 번호 차이가 (2,1)의 열 번호와, 다른 퀸의 열 번호의 차이와 같다면 대각선상에 위치한 것입니다.
따라서 이러한 상황에서도 현재 탐색중인 위치와, 1차원 배열의 값을 통해서 넘어갈 수 있습니다.
퀸을 놓는 과정을 재귀적으로 구현하고, 위처럼 1차원 배열만을 활용하여 다시 구현해 보니
코드를 간결하게 짤 수 있었습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <stdlib.h>
int count = 0;
int n;
int board[15];
// 유망한지 판단하는 함수
int promising(int cdx) {
// 같은 열이면 안되고, 대각선상에 있어서도 안 된다.
for (int i = 0; i < cdx; i++) {
if (board[cdx] == board[i] || cdx - i == abs(board[cdx] - board[i])) {
return 0;
}
}
return 1;
}
// nqueen 알고리즘 수행
void nqueen(int cdx) {
// cdx가 마지막 행까지 수행하고 여기까지 오면, 찾기 완료
if (cdx == n) {
count++;
return;
}
for (int i = 0; i < n; i++) {
board[cdx] = i; // cdx번째 행, i번째 열에 queen을 놓아본다.
// 이후 그 행에 둔 것에 대한 유망성을 판단한다.
if (promising(cdx)) { // 그 자리에 두어도 괜찮았다면,
nqueen(cdx + 1); // 그 다음 행에 대해 퀸을 놓는 것을 해 본다.
}
}
}
int main() {
scanf("%d", &n);
nqueen(0);
printf("%d", count);
}