[백준] 9963번 : N - Queen (C++)

https://www.acmicpc.net/problem/9663

 

문제

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

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

입력

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

출력

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

예제 입력 1 

8

예제 출력 1 

92

---

N개의 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 구하는 유명한 문제이다.

제한시간이 10초로 그냥 단순하게 백트래킹을 하면 되는 문제

 

처음에는 board[n][n]을 만들고 퀸이 배치 될 때 마다 board[i][j] + 퀸이 공격 가능한 칸에 +1을 하여 방문했음을 표시하였지만, 칸마다 방문여부를 표시하는 것은 메모리 낭비였다.

 

키포인트는 각 row, colomn, dialog마다 하나의 퀸밖에 두지 못하므로 그냥 col, dial배열을 설정하여 1, 0 으로 방문 여부만 체크하면 메모리를 훨씬 아낄 수 있다는 점이다.

 

↗️방향 :  row + col의 합이 동일한 값들은 같은 dialog를 공유한다.

↖️방향 :  rowd와 col의 차가 동일한 값들이 같은 dialog를 공유한다.

#include <bits/stdc++.h>

using namespace std;

int n ;  

int res = 0;

bool col[16], diag1[32], diag2[32];

void solve(int row) {

    if (row == n) {

        res++;

        return;

    }

    for (int c = 0; c < n; c++) {

        if (!col[c] && !diag1[row + c] && !diag2[row - c + n - 1]) {

            col[c] = diag1[row + c] = diag2[row - c + n - 1] = true;

            solve(row + 1);

            col[c] = diag1[row + c] = diag2[row - c + n - 1] = false;

        }

    }

}

int main() {

    cin>>n;

    solve(0);

    cout << res << endl;

}