백준 9663 : N-Queen

N-Queen 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

10 초

128 MB

58993

29418

19313

49.365%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 복사

8

예제 출력 1 복사

92

 

힌트

 

 

코드 

#include <iostream>
using namespace std;
int n;

int vx[16], vy[16];

int dfs(int y, int x) {


for (int i = 0; i < y; i++) {
if (y == vy[i])return 0;
if (x == vx[i])return 0;
if (abs(x - vx[i]) == abs(y - vy[i]))return 0;
}

if (y == n - 1) {
return 1;
}

vy[y] = y, vx[y] = x;

int answer = 0; 
for (int i = 0; i < n; i++) {
answer += dfs(y + 1, i);
}
return answer;

}

int main() {

cin >> n;
int answer = 0;

for (int i = 0; i < n; i++) {
answer += dfs(0, i);
}//0 1 2 3 4 5 6 
cout << answer;
return 0;
}

N-Queens문제는 백트래킹을 설명하는 대표적인 알고리즘이다

백트래킹은 dfs+ 가지치기를 혼합한 개념으로 

가지를 쳐서 불필요한 계산을 줄임으로서 dfs의 연산 속도를 높여준다.