https://www.acmicpc.net/problem/9663
문제
> N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
> N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.접근
일차원벡터를 만들어 체스판의 행을 나타낸다고 정의해준다.
그럼 각 인덱스는 행 번호를 말하고, 인덱스의 값은 열을 말한다.
퀸은 체스에서 8방향으로 이동할 수 있다. 따라서 어떤 퀸을 배치하면 그 좌표 기준 8방향에 해당하는 모든 좌표에는 다른 퀸이 올 수 없다.(오면 공격받으니까)
그럼 이를 검증하는건 벡터의 인덱스별로 각각의 값을 비교했을 때 두 값이 같다면 행은 다르지만 같은 열에 있다는 뜻이므로 이 경우를 걸러주고, 또 어떤 두 좌표가 대각선상에 있다는건 두 좌표의 x,y좌표를뺀값이 동일한가로 따져줄 수 있다. (대각선이라면 (x2-x1) == (y2-y1))
그래서 두 값이 동일하다면 걸러준다.
여기서 걸러지지 않으면 재귀로 다음 행에 어디 놓을 수 있는지 위 과정을 반복해 따져준다.
그래서 탈출조건에 만족하면 모든 행에 배치했다는 뜻이므로 cnt를 누적한다.
문제해결
> 퀸의 위치를 저장할 chess 벡터를 선언하고 퀸을 배치할 메소드 Chess를 정의한다.
> 인자로 받는 n은 행 번호를 뜻하고 이 n체스판의 크기 N과 같아지면,
즉 0부터 N-1까지(끝까지) 다 유효한 자리가 있어 채우고 난 뒤 N까지 오면 가능한 경우이므로 cnt를 누적한다.
> 퀸을 배치하는 부분에선 반복문 i는 열 번호를 말한다.
chess[n] = i를 통해 n행 i열에 퀸을 배치하고 검증을 한다.
> chess[n] == chess[i]를 통해 퀸이 같은 열에 놓여있다면을 검증하고 n-i, abs(chess[n]-chess[i])를 통해 좌표의 y2-y1과 x2-x1이 같은지 검증한다.(대각선 관계인가)
> 위 두 조건에 걸리지 않으면 서로 공격이 불가능한 문제에서 원하는 상태이므로 다음 행에 퀸을 배치하기 위해 재귀로 행+1을 넘겨주며 호출한다.
> 끝까지 다 돌고누적된 cnt를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N;
vector<int> chess; //체스판의 행
int cnt = 0;
void Chess(int n)
{
if (n == N)
{
cnt++;
return;
}
for (int i = 0; i < N; i++)
{
bool valid = true;
chess[n] = i; //n은 행, chess[n] 은 열
for (int i = 0; i < n; i++)
{
if (chess[n] == chess[i])
{
valid = false;
break;
}
if (n - i == abs(chess[n] - chess[i]))
{
valid = false;
break;
}
}
if(valid) Chess(n + 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
chess.resize(N);
Chess(0);
cout << cnt << '\n';
}
후기
처음에 체스판을 부울형으로 만들고 0,0부터 N-1,N-1까지 반복문으로 돌며 각각의 좌표에 퀸을 배치했을 때 다음 퀸이 불가능한 영역을 전부 true로 주면서 범위를 좁혀나가며 재귀를 하는데 만약 N개를 놓으면 개수 누적, 못놓으면 다음 재귀로 가도록 했다.
이렇게 하니 가능한 각 좌표마다 부울형chess판을 복제해서 매번 넘겨주고, 또 재귀로도 체스판 벡터가 넘어가니 N이 작을 땐 잘 됐는데 좀 커지니 연산이 안됐다.
스마트하게 생각하는 법을 기르도록 하자
