[백준 9663] 알고리즘 31일차 : N-Queen

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

9663번: N-Queen

백트래킹 C++

백트래킹의 고전 문제 N-Queen 문제이다. 아무리 그래도 규칙 설명 한 줄이 없다.

 

접근방법

알고리즘 수업 때 배운 로직을 사용했다.

각 행에 퀸이 놓여있는 열 인덱스를 담은 col 배열을 전역변수로 선언해두고

한 행 안에서 각 열에 대한 반복문을 돌면서 퀸을 놓고 함수를 재귀 호출한 뒤

다시 퀸을 거두면서 백트래킹을 구현했다.

 

promising을 함수 초반에 호출하여 검사하는게

직관적으로 와닿지 않아서 퀸을 놓기 직전에 promising을 호출하는 방법으로

다시 구현했다.

퀸을 일단 놓고 공격받지 않는지 검사한 뒤 공격받지 않으면 그대로 놓은 상태에서

queen함수를 재귀호출한다. 이후 퀸을 다시 거두면서 백트래킹한다.

그럼 promising함수를 더 많이 호출하게 되는게 아닌가 싶었지만

queen함수를 그 만큼 덜 호출하게 된다.

되게 미세하지만 시간도 줄고 코드도 줄었다. (코드 왜 줄었지..?)

promising 함수는 같은 열에 퀸이 있는지, 대각선에 퀸이 있는지를 검사했다.

소스코드

#include <iostream>
using namespace std;
int N;
int col[15] = {0,};
int result = 0;

bool promising(int row){
    for(int r = 0 ; r < row ; r++){
        if(col[r] == col[row] || abs(col[row]-col[r]) == row - r)
           return false;
    }
    return true;
}

void queen(int cnt){
    if(cnt == N){
        result++;
    }
    for(int c = 0 ; c < N ; c++){
        col[cnt] = c;
        if(promising(cnt)){
            queen(cnt+1);
        }
        col[cnt] = 0;
    }
}
int main(){
    cin >> N;
    queen(0);
    cout << result;
    return 0;
}