시작

이번문제는 상당히 어려운 문제다. 이 문제는 특히 엄청나게 생각하면서 풀었는데 한번 확인해보자. N퀸 문제는 오래되었다면 오래된 알고리즘 문제다. 그럼 한번 문제를 살펴보자면, N을 입력 받고 N*N의 판에서 N개의 퀸을 나두었을때 서로 공격이 안될 경우의 수를 구하는 문제이다. 그렇다면 체스에서 퀸의 역할을 알아야된다. 퀸은 8방향을 아무 조건없이 이동할 수 없다. 이제 한번 알아보자

예외 확인 사항

1. 우선 같은 열에 있으면 안됨
2. 대각선에 존재한다면 안됨

이런 예외 확인 사항이 있는데 이걸 생각하면서 한번 풀어보자면

알고리즘

1. n개의 배열을 만든다
2. 0부터 시작해 같은 열에 퀸이있으면 return
3. 같은 열에 없어도 대각선에 있으면 return

이문제를 재귀로 푼다면 시각적으로 표현하였을때는 이런 모습일 것

코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>

using namespace std;

int n, result = 0;
vector<int> board;

int Check(int cnt) {
	// 현재 열을 체크
	for (int i = 0; i < cnt; i++) {
		// 같은 열에 있거나, 대각선에 있으면 안됨
		if (board[cnt] == board[i] || abs(cnt - i) == abs(board[cnt] - board[i])) return 0;
	}
	return 1;
}

void Solved(int cnt) {
	// 만약 n개가 다채워졌으면 종료
	if (cnt == n) {
		result++;
		return;
	}
	// n번동안 반복
	for (int i = 0; i < n; i++) {
		//일단 보드에 넣어보기
		board[cnt] = i;
		//만약 넣을 수 있다면?
		if (Check(cnt)){
			// 다음에도 넣어서 확인
			Solved(cnt + 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	board.resize(n);
	Solved(0);
	cout << result;
}

참고

위키피디아

나무위키