[C++] 백준 9663번 - N-Queen (백트래킹) 문제

#골드4

 

 

백준 9663번 문제는 백트래킹의 대표 문제인데, 백트래킹을 돌 조건식만 잘 세울 수 있다면 문제없이 풀 수 있을 것이다.

자네, 체스를 좀 해보았는가..?

 

 

문제 링크

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

9663번: N-Queen

 

알고리즘

이 문제의 핵심은 두 개이다.

1. 같은 행에는 퀸 1개만 놓을 수 있다는 것

2. 두 개의 퀸이 대각선에 존재하는지 체크하는 식이다.

 

같은 행에 퀸은 한개만 존재하기 때문에, col이라는 배열에서 i번째 원소의 값은 NxN 체스보드 위에서 퀸이 몇번째 열에 존재하는지 일 것이다.

그리고 대각선에 있는지는 기울기가 1이라고 생각하면 되므로, x좌표끼리의 차와 y좌표끼리의 차이가 같은지 비교하면 된다. 같다면 대각선 상에 존재하는 것이고, 같지 않다면 아닌 것이다. 

 

이렇게 아이디어를 정리했다면, 기본적인 백트래킹 코드를 구현하고 ifValid 함수를 만들어 조건을 검사하도록 하고 통과할 시 다음 행에 퀸을 놓도록 한다.

 

 

코드

#include <iostream>
#include <cmath>
#define MAX 15

int col[MAX];
int n;
int ans = 0;
using namespace std;

bool ifValid(int level){
    for(auto i=0;i<level;i++){
        // 1. 같은 행에 있는지
        // 2. 대각선에 있는지
        if(col[i] == col[level] || abs(col[level]-col[i]) == level-i){
            return false;
        }
    }
    return true;
}

void nqueen(int x){
    if(x==n){
        ans++;
        return;
    }
    for(auto i=0; i<n; i++){
        col[x]=i;
        if(ifValid(x)){
            nqueen(x+1);
        }
    }
   
}

int main()
{
    cin >> n;
    nqueen(0);
    cout << ans << '\n';

    return 0;
}

 

제출 결과