[백트래킹/ N-queen(C++)] 9663 N-Queen

문제

문제를 보고 꽤나 당황했다.. 저는 체스 규칙도 모르는데요....

유명한 문제고 백트레킹의 대표적인 문제이기 때문에 이번 기회에 완전히 정복하고 가자는 마음으로 풀어보겠다!

 

문제 해석

체스 규칙에서 퀸은 자신을 기준으로 일직선상과 대각선 방향에는 아무것도 놓여있으면 안된다. 퀸이 그곳으로 다 움직일 수 있다.

 

우선 이 문제에서는 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다고 생각하는 것이 중요하다.(같은 행에는 퀸이 놓일 수 없음)

 

풀이 방식 

그리고 이 문제는 이차원 배열을 만들 필요 없이, 일차원 배열을 만든 후, 각 행의 몇번째 열에 퀸이 있는지를 저장하는 방식으로 풀 수 있다.

 

한 행마다 하나의 퀸을 배치해가면서, 총 배치 행수가 N이 되면, 경우의 수를 1개씩 올려주면 된다. 

 

=> 따라서 재귀함수의 매개변수에는 현재 몇번째 행을 채우고 있는지를 기록하는 인자가 필요하다.

 

퀸을 배치해가면서 따져야하는 것은 앞에서 배치한 퀸이 다른 퀸과 같은 행 또는 같은 열에 있는가, 그리고 대각선에 위치해 있는가이다.

 

TIP❗️ 대각선에 존재하는 좌표일 경우 x, y의 차가 동일하다. 

 

풀이 코드

#include <iostream>

#define MAX 14
using namespace std;

int n;

int cnt = 0;

int queen_column[MAX];

bool can_go(int row){
    //전 행에 놓인 퀸들과 충돌하지 않는 지 => 그러므로 행의 중복 여부는 검사하지 않아도 된다.
    for(int i=0; i<row; ++i){
        if ((queen_column[i] == queen_column[row]) || (row - i == (abs(queen_column[row] - queen_column[i])))){
            return false;
        }
    }
    return true;
}

void nqueen(int row){

    // n번째 행까지 n개의 퀸을 놓는 하나의 경우의 수를 찾았다면, 함수 종료
    if (row == n){
        cnt++;
        return;
    }
    else{
        for (int col=0; col<n; ++col){//현재 행에서 모든 열에 대해 검사한다.
            queen_column[row] = col;
            // 현재 행, 열 위치가 퀸의 위치로 문제 없다면, 다음 행 검사
            if (can_go(row)){
                nqueen(row + 1);
            }
            // 현재 행, 열 위치가 퀸의 위치로 문제가 있다면, 다른 위치를 찾아본다.(행을 바꿔가며)
        }
    }
}

int main(void){
    cin >> n;
    nqueen(0);
    cout << cnt;
    return 0;
}

 

참고 블로그: 

https://wooono.tistory.com/302

[Backtracking] 백준 9663번 N-Queen C++ 풀이