https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다.
Queen들이 서로 공격하는 조건은 다음과 같습니다.
- 같은 행에 위치
- 같은 열에 위치
- 대각선에 위치
같은 행에 위치하면 공격한다는 조건을 고려하여 볼 때, 한 행에 퀸은 한개만 존재한다는 것을 알 수 있습니다. 따라서 이차원배열이 아니라 일차원배열로 퀸의 위치를 나타내어도 상관이 없습니다. 예를 들어, row[2]=3; 은 2행 3열에 퀸이 존재한다는 의미입니다.
먼저 N을 입력받은 후, 탐색을 진행하는 nqueen함수에 0을 넣습니다.(0번째 행부터 탐색한다는 뜻입니다)이때 nqueen의 매개변수는 현재 몇번째 행을 진행중인지를 보여주는 인자입니다.
만약 nqueen의 매개변수 x와 n이 같으면, 하나의 경우의 수를 충족하는 것이므로 경우의 수를 추가하고 이전 노드로 돌아갑니다. 아니라면 현재 행에 0부터 n까지의 숫자를 넣으면서 유망성을 체크합니다.
만약 유망하다면, 다음 행을 탐색합니다.
//
// Copyright (c) 2021 HyeJin Shin All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int ans=0;
int row[16];
bool check(int x) { //유망성 체크
for(int i=0;i<x;i++){
if (row[i]==row[x]||abs(i-x)==abs(row[i]-row[x])) {return false;} //같은 열이거나 대각선인 경우 return false (같은 행은 올 수가 없음)
}
return true;
}
void nqueen(int x){
if(x==n){ //하나의 경우의 수 충족
ans++;
return; //이전 노드로 돌아감
}
else {
for(int i=0;i<n;i++){
row[x]=i;
if(check(x)){ //유망성을 체크한 뒤
nqueen(x+1); //그 다음 행 탐색
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
nqueen(0);
cout<<ans;
}