[백준 9663] N-Queen

 오랜만에 쉬운 문제

  N-Queen 문제이다.

 퀸이 서로 공격하지 못하도록 위치할 수 있는 모든 경우의 수를 구하는 문제이다.

 1. 퀸의 위치를 나타는 배열 col[]을 사용한다.

         col[x] = y   // x행 y열에 퀸이 위치한다는 표시

2. 퀸이 서로 공격할 수 있는 경우 (예외처리를 해주어야 함)

 col[i] == col[cur]      // 같은 열에 존재하는 경우

(i - cur) == abs(col[i] - col[cur])    // (행 - 행) == (열 - 열)

*(출처 : 위키피디아)

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

소스코드

#include<iostream>
#include<cmath>
 
using namespace std;
 
int col[16];                                // col[x] => x행의 n번째 열에 퀸이 존재
int n, cnt=0, ans;                                    // 체스판의 크기 
 
bool check(int cur){                            // 조사할 체스판의 행 
    for(int i = 1; i < cur; i++){
        // col[i] == col[curr] => 같은 행이다. 
        // (cur - i) == abs(col[cur] - col[i]))은 퀸과 퀸 위치 x,y 값의 차이가 같다. => 대각선이다. 
        if(col[i] == col[cur] || (cur - i) == abs(col[cur] - col[i]))
            return false;
    }
    return true;
}
void solve(int cur){
    if(cur == n+1){                    // 모든 행을 시도하여 성공했을 때 
        ans++;                    // ans++
        return;                    // 종료 
    }
    for(int i = 1; i <= n; i++){
        col[cur] = i;                // 퀸을 위치 
        if(check(cur)){                // 퀸을 위치 시켜도 되는가? 
            solve(cur+1);            // 다음 행을 시도 
        }
    }
}
int main(void){
    cin >> n;
    solve(1);                    // 1행부터 시작한다. 
    cout << ans;
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.