백준 9663. N-Queen
알고리즘 중급 문제 중 531 - 브루트 포스 - 재귀(연습)
1. 간단 설명
N * N 크기의 체스판 위에,
N개의 퀸을 서로 공격할 수 없게 놓아야한다
놓을 수 있는 경우의 수를 구하는 문제
2. 예시
N = 4인 경우
1
2
3
4
1...
....
....
....
1번 자리에 첫번째 퀸을 놓으면
1
2
3
4
1***
**..
*.*.
*..*
다음과 같은 칸에는 다른 퀸을 놓을 수 없게된다
1
2
3
4
1***
**2*
****
*3**
두번째 퀸을 2번 자리에, 세번째 퀸을 3번자리에 놓으면 4번 퀸을 놓을 수 없다
이런식으로 퀸을 각각 놓아보고, 모든 퀸을 놓을 수 있는 경우의 수를 찾는 문제
3. 알고리즘
처음 시도한 방법
(0,0)부터 빈자리가 있다면 퀸을 놓아보는 방식을 사용함
2차원 배열을 통해서, 퀸의 공격 범위를 모두 표시하는 방식을 사용했음
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for y in 0 ~ N
for x in 0 ~ N 에서
퀸을 놓을 수 있다면
이 자리에 퀸을 놓고, 이 퀸의 공격 범위를 모두 표시한다
이후 다시 재귀함수 호출
(y,x)에 퀸을 놓았을때 퀸의 공격범위
(y-1, x-1), (y-2, x-2), ... y또는 x가 0보다 작을때까지
(y-1, x), (y-2), ... , (0,x)
(y-1, x+1), (y-2, x+2), ... , y가 0보다 작거나, x가 N-1보다 클때까지
(y, x-1), (y, x-2) , ... x가 0보다 작을때까지
(y, x+1), (y,x+2), ... , x가 N-1보다 클때까지
(y+1, x-1), (y+2, x-2), ... , y가 N-1보다 클때까지, 혹은 x가 0보다 작을때까지
(y+1, x), (y+2, x) , ... , y가 N-1보다 클때까지
(y+1, x+1), (y+2, x+2), ... , y또는 x가 N-1보다 클때까지
그러나 몇가지 문제가 발생했는데
- 맵을 백업하고 복원하는 과정에서 문제 발생
- 일일히 공격 범위를 지우는데 비효율적임
결국 풀이를 참고했다
가장 중요한 아이디어는 i번째 퀸을 i번째 행에 놓는다
즉, 첫번째 퀸은 첫번째 행에만 놓을 수 있다.
어짜피 가로는 다른 퀸들은 못 놓으니, 다음 퀸은 다음 행에 놓을 수 밖에 없음
이를 이용하면 2차원 배열 필요 없이 1차원 배열에 현재 퀸의 좌표를 기록하여 해결할 수 있다
(2,0,3,1) 은 첫번째 퀸은 (0,2), 두번째 퀸은 (1,0), 세번째 퀸은 (2,3), 네번째 퀸은 (3,1)에 놓는다는 뜻
또한 이 방법은 퀸을 놓을 때 체크해야할 범위도 줄어든다는 장점이 있다
어짜피 행은 못 놓기 때문에, 대각선 방향과 열 방향에 걸리는 퀸이 있는지만 체크하면 된다
전체적인 알고리즘은 다음과 같다
1
2
3
4
5
6
1. N을 입력받는다
2. 재귀함수를 호출한다
2-1. 만약 모든 퀸을 놓았다면, 정답의 개수를 1 늘린다
2-2. 현재 level번째의 행의 i번째 열에 퀸을 놓아본다
2-3. 퀸을 놓아도 문제가 없는지 체크한다
2-4. 문제가 없다면 다음 퀸을 놓는다
필요 변수
int N ( N <= 15)int board[16]int answer
4. 소스코드
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
#include <iostream>
using namespace std;
int N;
int answer = 0;
int board[16];
bool check(int level) {
// 이번에 놓은 퀸은 같은 열에 있어서도 안되고, 대각선 상에도 있어선 안된다
for (int i = 0; i < level; i++) {
if (board[level] == board[i] || // 같은 열에 놓은 퀸이 있는지 체크
level - i == abs(board[level] - board[i])) // 이전 퀸과 대각선상 걸리는지 체크
return false;
}
return true;
}
void nqueen(int level) {
if (level == N) {
answer++;
return;
}
for (int i = 0; i < N; i++) {
board[level] = i; // level번째 행의 i번째 열에 퀸을 놓는다
if (check(level)) { // 퀸을 놓아도 문제 없다면 계속 놓음
nqueen(level + 1);
}
}
}
int main() {
cin >> N;
nqueen(0);
cout << answer;
}
무식하게 시도했다가 실패한 처음 방법
퀸 놓는 방법도 최적화 하지 않고 그냥 막 했다가 도중에 아닌것 같아서 빠르게 포기함
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <memory.h>
using namespace std;
int N;
int map[16][16];
int backup[16][16];
int answer = 0;
// y, x에 퀸을 놓았을 떄, 공격범위에 해당하는 칸을 지우는 함수
void QueenRange(int level, int yy, int xx) {
int dy = yy, dx = xx;
while ((0 <= dy && dy <= N - 1) && (0 <= dx && dx <= N - 1)) {
if(map[dy][dx] == 0)
map[dy][dx] = level + 1;
dy -= 1;
dx -= 1;
}
dy = yy, dx = xx;
while (0 <= dy && dy <= N - 1) {
if (map[dy][dx] == 0)
map[dy][dx] = level + 1;
dy -= 1;
}
dy = yy, dx = xx;
while ((0 <= dy && dy <= N - 1) && (0 <= dx && dx <= N - 1)) {
if (map[dy][dx] == 0)
map[dy][dx] = level + 1;
dy -= 1;
dx += 1;
}
dy = yy, dx = xx;
while (0 <= dx && dx <= N - 1) {
if (map[dy][dx] == 0)
map[dy][dx] = level + 1;
dx -= 1;
}
dy = yy, dx = xx;
while (0 <= dx && dx <= N - 1) {
if (map[dy][dx] == 0)
map[dy][dx] = level + 1;
dx += 1;
}
dy = yy, dx = xx;
while ((0 <= dy && dy <= N - 1) && (0 <= dx && dx <= N - 1)) {
if (map[dy][dx] == 0)
map[dy][dx] = level + 1;
dy += 1;
dx -= 1;
}
dy = yy, dx = xx;
while (0 <= dy && dy <= N - 1) {
if (map[dy][dx] == 0)
map[dy][dx] = level + 1;
dy += 1;
}
dy = yy, dx = xx;
while ((0 <= dy && dy <= N - 1) && (0 <= dx && dx <= N - 1)) {
if (map[dy][dx] == 0)
map[dy][dx] = level + 1;
dy += 1;
dx += 1;
}
/*
(y - 1, x - 1), (y - 2, x - 2), ... y또는 x가 0보다 작을때까지
(y - 1, x), (y - 2), ..., (0, x)
(y - 1, x + 1), (y - 2, x + 2), ..., y가 0보다 작거나, x가 N - 1보다 클때까지
(y, x - 1), (y, x - 2), ... x가 0보다 작을때까지
(y, x + 1), (y, x + 2), ..., x가 N - 1보다 클때까지
(y + 1, x - 1), (y + 2, x - 2), ..., y가 N - 1보다 클때까지, 혹은 x가 0보다 작을때까지
(y + 1, x), (y + 2, x), ..., y가 N - 1보다 클때까지
(y + 1, x + 1), (y + 2, x + 2), ..., y또는 x가 N - 1보다 클때까지
*/
}
// (y,x)에 level번째 퀸을 놓는 함수
void PutQueen(int level, int y, int x) {
if (level == N - 1) {
answer++;
return;
}
// 놓을 수 있는 자리에 다음번째 퀸을 놓기
for (int yy = 0; yy < N; yy++) {
for (int xx = 0; xx < N; xx++) {
if (map[yy][xx] == 0) {
memcpy(backup, map, sizeof(map)); // 기존 맵 저장
QueenRange(level, yy, xx); // 범위에 해당하는 칸 지우기
PutQueen(level + 1, yy, xx); // 재귀
memcpy(map, backup, sizeof(map)); // 복구
}
}
}
}
int main() {
cin >> N;
// 0, 0 부터 퀸을 놓아본다
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
PutQueen(0, y, x);
}
}
cout << answer;
return 0;
}
참조
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.