[Algorithm] 백준 9663 N-Queen c++

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

9663번: N-Queen

 

풀이

백트래킹

• 체스판의 행을 기준으로 i번째 행에 Queen을 놓으면, i+1번째 행으로 넘어간다.
• 배열 x는 인덱스는 체스판의 row(행)를 의미하고, 값은 체스판의 col(열)을 의미한다.
• 예를 들어, x[1] = 2가 의미하는 것은 "체스판[1][2] 자리에 Queen이 있다"는 것이다.
• i+1번째 행에 Queen을 놓을 자리가 없다면 i번째 행으로 다시 돌아가 다음 열부터 탐색한다. (백트래킹)
• 체스판[row][col]의 위치에 Queen이 위치할 수 있는지 판단하는 함수는 isPlaceAt이다. 현재 행과 열을 기준으로 같은 열, 왼쪽 대각선 위, 오른쪽 대각선 위에 다른 Queen이 존재한다면 false를 반환하고 그렇지 않으면 true를 반환한다.
• 체스판의 마지막 행까지 Queen이 놓였다면 cnt++한다.

예시 ) N = 4 경우, row2 까지 Queen 놓은 상황
1 ~ 4. row3의 0번째 col부터 Queen을 놓을 수 있는지 판단한다.
5. 현재 상황에서 row3에는 Queen을 놓을 수 있는 곳이 없다. -> row2로 돌아간다.
6. row2의 다음 열인 col3에 Queen을 놓아본다. 가능하다.
7. x를 업데이트한다.
8. row2까지 Queen이 놓여있으므로 다시 row3에 Queen을 놓을 수 있는지 판단한다.

N = 4 경우, row2 까지 Queen 놓은 상황

 

소스코드

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

int n, cnt;
int x[16];

//현재 자리에 Queen이 위치할 수 있는지 판단
bool isPlaceAt(int row, int col){
    for(int i=0; i<row; i++){
        //같은 열에 Queen 존재 확인
        if(x[i] == col) return false;
        //왼쪽 대각선에 Queen 존재 확인
        if(x[i] == col - (row - i)) return false;
        //오른쪽 대각선에 Queen 존재 확인
        if(x[i] == col + (row - i)) return false;
    }
    return true;
}

void backtrack(int row){
    if(row == n) cnt++;

    for(int col=0; col<n; col++){
        if(isPlaceAt(row, col)){
            x[row] = col;
            backtrack(row + 1);
        }
    }
}

int main(){
    cin>>n;
    backtrack(0);
    cout<<cnt<<endl;
    return 0;
}