250x250
반응형
Notice
Recent Posts
Recent Comments
Link
N
(백준 c++) 9663 N-Queen 본문
728x90
반응형
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
DFS를 배우기 좋은 N-Queen 문제.
현재 위치에 퀸을 놓을 수 있는지 확인하는 isTrue 함수
이 함수를 이용해 해당하는 위치에 퀸을 놓고 DFS를 통해 N개의 퀸을 놓을 수 있는 경우의 수를 구하면 된다.
isTrue는 현재 위치에서 팔방향으로 뻗는 자리를 모두 검사하여 true(퀸이 놓여 있는 경우)가 아니면 true를 리턴한다.
true가 리턴되면 그 자리에 퀸을 놓고, 계속 진행하면 된다.
#include <iostream>
#include <stdio.h>
using namespace std;
bool visited[15][15] = {false, };
int N = 0, ans = 0;
void dfs(int, int, int);
bool isTrue(int, int);
void dfs(int row, int col, int count)
{
if(count == N)
{
ans++;
return;
}
for(int i = 0; i < N; i++)
{
if(isTrue(row, i))
{
visited[row][i] = true;
dfs(row + 1, i, count + 1);
visited[row][i] = false;
}
}
}
bool isTrue(int row, int col)
{
//가로 검사
for(int i = 0; i < N; i++)
{
if(visited[row][i])
return false;
}
//세로 검사
for(int i = 0; i < N; i++)
{
if(visited[i][col])
return false;
}
//우측 상방 검사
for(int i = row, j = col; i >= 0 && j < N; i--, j++)
{
if(visited[i][j])
return false;
}
//우측 하방 검사
for(int i = row, j = col; i < N && j < N; i++, j++)
{
if(visited[i][j])
return false;
}
//좌측 상방 검사
for(int i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if(visited[i][j])
return false;
}
//좌측 하방 검사
for(int i = row, j = col; i < N && j >= 0; i++, j--)
{
if(visited[i][j])
return false;
}
return true;
}
int main() {
scanf("%d", &N);
dfs(0, 0, 0);
cout << ans;
return 0;
}
728x90
반응형
'백준 알고리즘' 카테고리의 다른 글
(백준 c++)1935 후위표기식2 (0) | 2020.12.27 |
---|---|
(백준 c++) 2580 스도쿠 (0) | 2020.09.21 |
(백준 c++) 15652 N과 M(4) (0) | 2020.09.21 |
(백준 c++) 15651 N과 M(3) (0) | 2020.09.21 |
(백준 c++) 15650 N과 M(2) (0) | 2020.09.21 |