백준 온라인 저지 9663 N-Queen

문제

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

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

입력

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

출력

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

 

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

#include<iostream>   using namespace std; bool col[15], dia1[30], dia2[30]; int n, arr[2] = {1, -1}; long long cnt;   void dfs(int line) {     if (line == n + 1) {         cnt++;         return;     }     for (int j = 1; j <= n; j++) {         if (col[j])continue;         int d1 = n + abs(line - j) * arr[line > j];         int d2 = line + j - 1;         if (dia1[d1] || dia2[d2])continue;         col[j] = dia1[d1] = dia2[d2] = true;         dfs(line + 1);         col[j] = dia1[d1] = dia2[d2] = false;     } }   int main() {     cin >> n;     dfs(1);     cout << cnt << '\n';     return 0; } Colored by Color Scripter

cs

 

모든 퀸이 서로 공격하지 못하게 놓기 위해서는 한 행, 한 열에 퀸이 각각 하나씩만 존재해야 한다는 결론이 나온다.

 

또한 퀸은 대각선으로 이동할 수 있기 때문에 한 대각선에는 퀸이 하나만 존재하거나 없어야 한다.

 

따라서 한 행에 퀸이 무조건 하나가 있어야 하고 함수를 행 기준으로 작성했기 때문에 행에 대한 확인을 굳이 할 필요가

 

없을 거 같았다.

 

따라서 열에 대해서만 반복문을 사용했는데 만약 퀸이 존재하는 행이라면 스킵하고 그렇지 않다면 대각선을 확인한다.

 

dia1은 왼쪽 위 ~ 오른쪽 아래 대각선을, dia2는 왼쪽 아래 ~ 오른쪽 위 대각선을 확인하기 위한 배열이다.

 

여기서도 반복문을 사용하지 않고 각각의 대각선에 대한 일련번호를 붙여서 시간을 조금이라도 줄이려고 했다.

 

두 대각선 모두 퀸이 존재하지 않으면 각각의 열과 대각선을 방문처리를 하고 다음 행을 탐색하는 식이다.

 

따라서 n번째 줄까지 확인하고 n+1번째 줄에 도착하면 cnt를 1 증가시키도록 코드를 작성했다.

 

1

print([1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596][int(input())-1])

cs

 

이건 숏코딩이다!! 재미로만 보자