https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
백트래킹의 대표적인 문제입니다.
퀸은 가로, 세로, 대각선 방향으로 어디든 갈 수 있으므로 서로 공격하지 못하게 하려면 위와 같은 형태가 되어야합니다.
문제에서는 위와 같은 형태가 몇 개 나올 수 있는지 출력하는 문제입니다.
x을 1씩 올려가면서 dfs를 돌리고 x,y 위치에서 y방향, 대각선 방향의 위치에 다른 퀸이 놓여져 있는지 체크 후에 놓는 방식으로 하였습니다.
y방향을 열을 나타내고, 대각선 방향은 /, \방향이 있습니다.
우선 좌표가 이런식으로 되어있습니다.
y 좌표는 말 그대로 (x, y)에서 y좌표만 체크해주시면 되고
대각선좌표는 이런식입니다.
왼쪽은 /방향 (x + y)를 나타낸것이고, 오른쪽은 \방향 (x - y + N - 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
|
#include <iostream>
using namespace std;
bool col[16], Left[27], Right[27];
int N, ans;
void dfs(int x) {
if (x == N) {
ans++;
return;
}
for (int y = 0; y < N; y++) {
if (col[y]) continue;
if (Left[x + y] || Right[x - y + N - 1]) continue;
col[y] = true;
Left[x + y] = true;
Right[x - y + N - 1] = true;
dfs(x + 1);
Right[x - y + N - 1] = false;
Left[x + y] = false;
col[y] = false;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N;
dfs(0);
cout << ans << '\n';
return 0;
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 15650 N 과 M (2) (0) | 2021.01.26 |
|---|---|
| boj 15649 N 과 M (1) (0) | 2021.01.26 |
| boj 2580 스도쿠 (0) | 2021.01.22 |
| boj 1759 암호 만들기 (0) | 2021.01.22 |
| boj 1062 가르침 (0) | 2021.01.22 |