[백준 - 9663] N-Queen - C++

분류: 백트래킹 /

 

문제

문제 링크

문제 설명

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

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

입력

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

출력

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

 

풀이

- 내 풀이

#include <iostream>
#include <vector>
using namespace std;

struct xy { int x, y; };
int n, ans;
vector<xy> queens;
bool cols[15];

bool checkDiagonal(int r, int c) {
    for(xy p:queens) 
        if(abs(r - p.x) == abs(c - p.y)) 
            return true;
    return false;
}
void backTracking(int r) {
    if(r == n) {
        ans++;
        return;
    }
    for(int c=0; c<n; c++) {
        if(cols[c]) continue;
        if(checkDiagonal(r, c)) continue;
        cols[c] = true;
        queens.push_back({r, c});
        backTracking(r+1);
        queens.pop_back();
        cols[c] = false;
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    backTracking(0);
    cout << ans;
}

n개의 퀸을 보드에 놓는다면 퀸은 행과 열에 하나씩 올 수있고 하나만 있어야 한다.(one and only one)

따라서 행에서 열 하나를 골라 퀸을 놓고 다음 행에서 열을 골라 퀸을 놓는 식으로 마지막 행까지 모두 수행하면 n개의 퀸을 모두 배치한 것이다.

대각선은 기울기의 절댓값이 1인 것으로 확인했다.

`r`을 입력으로 받는 대신 `queens`의 사이즈를 사용해도 되지만 행을 기준으로 수행되는 것을ㄹ 더 명확하게 하기 위해 `r`을 썼다.

`cols`도 `list`로 만들어 남은 열로만 루프를 돌려도 된다. 사용하면 `erase` 백트래킹할 때 `push`. 순서는 상관 없으니 그냥 set으로 사용가능

 

- 다른 사람 풀이

#include <iostream>
using namespace std;

int n, ans;
bool cols[14];
bool diagonals[2][29];

void backTracking(int r) {
    if(r == n) {
        ans++;
        return;
    }
    for(int c=0; c<n; c++) {
        if(cols[c] || diagonals[0][r+c] || diagonals[1][r-c+n-1]) continue;
        cols[c] = diagonals[0][r+c] = diagonals[1][r-c+n-1] = true;
        backTracking(r+1);
        cols[c] = diagonals[0][r+c] = diagonals[1][r-c+n-1] = false;
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    backTracking(0);
    cout << ans;
}

대각선에 인덱스를 부여해 column처럼 배열로 대각선을 확인한다.