반응형
문제링크:https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
dfs문제이고 백트래킹에서 대표적인 문제입니다.
15X15체스판까지 가능합니다.
하지만 dfs 구현시 함수에서 NxN번 반복하면 당연히 시간초과입니다.
다른방법을 생각해야합니다.
퀸은 자기의 양옆과 대각선 모두 이동이 가능합니다. 즉 행단위로 검사해도 괜찮습니다. 어차피 퀸이 있는 행에는 퀸이 있을 수 없기떄문입니다. 그렇기 때문에 열값은 count값을 사용합니다. ( 퀸이 체스판에 있을때마다 1씩증가)
n=4라면 답은 2입니다.
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
우선 정답코드입니다.
#include <iostream>
using namespace std;
int n = 0, result = 0;
bool visited[15][15] = { 0 };
bool available(int i, int cnt) {
int x, y;
for (x = 0; x < cnt; x++) {
if (visited[i][x]) return false;
}
for (x = cnt - 1, y = i - 1; y >= 0; x--, y--) {
if (visited[y][x]) return false;
}
for (x = cnt - 1, y = i + 1; y < n; x--, y++) {
if (visited[y][x]) return false;
}
return true;
}
void dfs(int cnt) {
if (cnt == n) {
result++;
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i][cnt] && available(i, cnt)) {
visited[i][cnt] = 1;
dfs(cnt + 1);
visited[i][cnt] = 0;
}
}
}
int main(){
cin >> n;
dfs(0);
cout << result << endl;
return 0;
}
아래가 재귀루트입니다.
for (int i = 0; i < n; i++) {
if (!visited[i][cnt] && available(i, cnt)) {
visited[i][cnt] = 1;
dfs(cnt + 1);
visited[i][cnt] = 0;
}
}
행은 0~n-1 까지 이동하며 검사하고 열값은 체스판에 퀸을 올려놓을때 마다 1씩증가하며 위치를 찾습니다.
아래는 검사함수입니다.
bool available(int i, int cnt) {
int x, y;
for (x = 0; x < cnt; x++) {
if (visited[i][x]) return false;
}
for (x = cnt - 1, y = i - 1; y >= 0; x--, y--) {
if (visited[y][x]) return false;
}
for (x = cnt - 1, y = i + 1; y < n; x--, y++) {
if (visited[y][x]) return false;
}
return true;
}
자신의 왼쪽에 퀸이 있는지 확인하는 과정입니다.
반응형
'알고리즘 > DFS' 카테고리의 다른 글
| [백준] 14267-내리 칭찬(C++) (0) | 2021.01.01 |
|---|---|
| [백준] 2580-스도쿠(C++) (0) | 2020.08.19 |
| [백준] 2573-빙산(C++) (0) | 2020.06.09 |
| [백준] 1987-알파벳(C++) (0) | 2020.06.09 |
| [백준] 1062-가르침(C++) (0) | 2020.05.05 |