[백준/BOJ] 9663 N-Queen (c++)

[백준/BOJ] 9663 N-Queen (c++)

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

2025.02.21 - [Competitive Programming] - 09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle

09. 완전 탐색 (Complete Search, c++) - Backtracking, Meet in the Middle

---

최대 15*15의 체스판에 Queen을 배치하는 경우의 수를 구하는 문제입니다.

 

백트래킹으로 row를 증가시켜가면서 column에 queen을 배치시켜보고, 모든 경우를 탐색해, N-1번째 row까지 queen이 배치가 되었다면 배치 가능한 경우로 갯수를 세어줍니다.

 

우선 같은 row에는 queen을 1가지만 배치할 수 있을텐데, 이 조건은 각 row에 대해 1개의 column에만 queen을 배치해보면서 백트래킹을 진행시킨다면 처리할 수 있습니다.

 

column 기준으로 queen을 배치할 수 없는 조건은 3가지 입니다.

그림 기준으로 번호가 같은곳에 이미 배치되었다면 배치할 수 없습니다.

 

1) 같은 열인경우

 

2) 왼쪽 대각선이 같은 경우, 3) 오른쪽 대각선이 같은 경우

 

위 3가지 조건을 확인하면서 조건에 해당하는 경우 해당 column에 queen을 배치시키고 다음 row로 진행시켜가면서 모든 경우를 확인하면 풀리게되는 문제입니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N, column[30], ldiag[30], rdiag[30], ans; 

int solve(int r) {
    if (r == N) {
        ans++;
        return 0;
    }
    for (int c=0; c<N; c++) {
        if (column[c] || ldiag[r+c] || rdiag[r-c+N-1]) continue;
        column[c] = ldiag[r+c] = rdiag[r-c+N-1] = 1;
        solve(r+1);
        column[c] = ldiag[r+c] = rdiag[r-c+N-1] = 0;
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    memset(column, 0, sizeof column);
    memset(ldiag, 0, sizeof ldiag);
    memset(rdiag, 0, sizeof rdiag);
    ans = 0;
    solve(0);
    cout << ans;
    return 0;
}