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

출처 : 9663번: N-Queen (acmicpc.net)

9663번: N-Queen

풀이 방법

퀸끼리는 같은 행, 열, 대각선에 놓일 수 없다.

위의 세 가지 조건중 하나(행)를 기준으로 잡고 퀸의 위치를 저장하였다.

(같은 행에는 2개의 퀸이 놓일 수 없기에 한 행에는 무조건 1개의 퀸만 배치)

그래서 배열 queen_col [i]는 i번째 row에 퀸이 몇 번째 col에 있는지를 뜻한다.

백트레킹을 통해 문제를 해결해 준다.

can함수를 통해 퀸을 배치할 수 있는지 확인해 준다.

같은 col인지는 queen_col배열을 통해 체크해준다

같은 대각선 인지 체크하는 방법은 퀸의 대각선은 기울기가 1 또는 -1인 직선이 된다.

이 특징을 이용해 각각의 절댓값 x좌표끼리의 차이와 y좌표끼리의 차이가 같으면 퀸의 대각선에 놓으려는 퀸이 위치한다고 판단하면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int n, ans;
int queen_col[15];

bool can(int row) {
    for (int i = 0;i < row;i++) {
        if (queen_col[i] == queen_col[row] || (row - i) == abs(queen_col[row] - queen_col[i])) {
            return false;
        }
    }
    return true;
}

void queen(int row) {
        if (row == n) ans ++; // n개의 퀸을 다 배치한 경우
        for (int i = 0;i < n;i++) { 백트레킹 이용
            queen_col[row] = i;
            if (can(row)) {
                queen(row + 1);
            }
        }
}

int main() {
    cin >> n;
    queen(0);
    cout << ans;
    return 0;
}