[C++] BOJ_9663 N-Queen

문제: 백준 9663 (c++)

풀이과정

---

N-Queen 문제는 queen들이 서로 공격하지 못하도록 놓는 경우의 수를 구하는 것이기에

백트래킹을 사용해 주면 간단하다.

첫 번째 행에 첫 번째 퀸을 배치하고 두 번째 행에 퀸을 배치하면서

가능한 열들을 모두 시도하는 것이다.

이때 필요한 코드가 아래의 코드이다.

---

if(i == queen[j] || abs(i-queen[j]) == num - j)

이 코드로 퀸들이 서로 충돌하는지에 대해 검사할 수 있다. abs를 이용하여 대각선도 확인할 수 있다.

저 공식을 사용하는 이유는 대각선은 두 퀸의 행과 열 차이가 같으면 대각선으로 연결되어 있다고 볼 수 있기 때문이다.

---

전체 코드이다.

#include <iostream> 
#include <math.h>
using namespace std ;

int n, cnt ;

int queen[16] ;

bool check ;

void search(int num){

    if(num == n){
        cnt++ ;
        return ;
    }

    for(int i = 0; i < n; i++){
        queen[num] = i ; 
        check = true ;

        for(int j = 0; j < num; j++){
            if(i == queen[j] || abs(i-queen[j]) == num - j){
                check = false ;
                break ;
            }
        }

        if(check) search(num + 1) ;
    }

}

int main(){

    cin >> n ;
    search(0) ;
    cout << cnt ;

}

Backtracking이란

해를 찾는 도중 막히면 되돌아가서 다시 해를 찾는 알고리즘이다.

모든 경우의 수를 고려하는 알고리즘으로 재귀를 활용한다.