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

문제링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

문제설명

N X N 크기의 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 경우의 수 구하기

 

직관적인 접근 - 완전탐색

체스판 위에 N개의 퀸을 놓을 수 있는 모든 경우의 수를 구하고 서로 공격할 수 없는 경우만 출력

 

문제점 - 시간초과

완전탐색으로 문제를 접근하면 O(N!) 의 시간복잡도가 소요된다. 따라서 N이 증가할때마다 기하급수적으로 성능이 떨어진다.

 

문제해결 - 백트래킹

퀸은 한 행에 하나만 두어야 한다. 따라서 한 행에 하나의 퀸만 차례로 두면서, 다음 행으로 이동한다.

다음행에 퀸을 둘 때는 이전 행에 둔 퀸이 같은열이나 대각선에 존재하는지 확인하고(유망함수 check()로 검사), 존재한다면

퀸의 위치를 한칸 옆으로 옮겨서 다시 확인해본다..(열 이동)(가지치기)

N개의 퀸을 모두 놓았으면 정답을 1 증가시키고 다른 경우의 수를 탐색한다.

 

소스코드

#include <iostream>;
using namespace std;
 
 
int answer = 0;     // 경우의 수를 기록할 변수
int n;              // 체스판 크기
int boardRow[15];   // 체스판 정보, 배열의 index = 체스판의 행, value = 해당 행에서 퀸을 놓은 열의 위치
 
// 퀸을 놓아도 되는지 확인하는 함수
bool check(int idx){
    // 0번 행부터 idx -1 번째 행까지 확인
    for(int i = 0; i&lt;idx; i++){
        if(boardRow[i]==boardRow[idx] || abs(boardRow[idx]-boardRow[i]) == idx-i)
            return false;
    }
    return true;
}
 
// 매개변수 idx = 현재 행의 인덱스
int backtracking(int idx){
    
    // idx가 n보다 크면 모든 행을 확인 한 것이므로 answer를 1 증가
    if(idx == n)
        return ++answer;
    
    // 어떤 열에 퀸을 놓을지 고르는 반복문
    for(int col=0; col&lt;n; col++){
        boardRow[idx] = col;    // 일단 퀸을 둠
        
        if(check(idx))
            backtracking(idx+1);     // 퀸을 놔서 문제가 없으면 다음행으로 이동
    }
    return 0;
}
 
int main(){
        
    cin >> n;
    
    // 탐색함수 호출
    backtracking(0);
    
    // 결과 호출
    cout << answer;
    
    return 0;
}