🖊️ 문제

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

---

🖊️ 풀이

전형적인 백트레킹 문제
사실 N-Queen 알고리즘은,, 작년에 누가 풀던걸 봐서 아 이거 나중에 풀어봐야지~ 하고 잊고있었던 문제였다.

다만, 처음에 큰 생각없이 2차원배열로 풀었고, 문제에 대해 제대로 이해하지 못했던 것 같다.

가장 중요한 점은,
퀸을 놓을 수 있는지 여부를 판단하는 것.
그리고 그 퀸을 놓는 여부를 판단하는 알고리즘을 설계하는 것.

퀸은 1열 당 1개씩만 놓을 수 있다.

같은 행, 열, 대각선에는 퀸을 놓을 수 없기 때문.
그래서 굳이 이차원 배열로 구현하지 않고,
열을 담는 일차원 배열 1개를 놓고, 해당 배열의 원소의 값들이 해당 열에 놓인 퀸의 행 위치로 한다.

---

알고리즘
일단 (0, 0)부터 시작한다.

1. a번째 열 b번째 행에 퀸을 놓는다.
2. 만약 해당 행에 퀸을 놓을 수 있다면, 다음 열(a+1열)로 넘어간다. (1로 되돌아감)
   2-1. 해당 행에 퀸을 놓을 수 없다면, 다음 행으로 넘어간다.

위 순서를 반복하며, 모든 열에 퀸이 채워지면 하나의 경우의 수가 생긴다.

이렇게 모든 열과 행에 퀸을 놓아보는 과정을 거친다.

퀸을 놓는 조건은 다음과 같다.
1. 같은 행에 퀸이 없을 것
2. 현재 위치 기준 대각선에 퀸이 없을 것

현재까지의 모든 퀸들에 대해, 위 조건을 대입해본다.

---

사실 풀 자신이 없어서, 구글링해보고 직접 구현해봤다.

생각하고, 풀고, 그걸 다시 글로 정리해보니 알겠다.
전형적인 백트래킹 (퀸을 놓을 수 없다면 다시 되돌아감(알고리즘 2-1))과, 완전탐색.

코딩테스트 시리즈 100번째 글인 만큼, 다시 처음으로 돌아가서 공부하는 마음으로 작성해봤다.

#include <iostream>
#include <memory>
using namespace std;

int N;
int arr[15];
int result = 0;

bool SetQueen(int idx)
{
	for (int i = 0; i < idx; i++) {
		if (arr[i] == arr[idx] || abs(idx - i) == abs(arr[idx] - arr[i])) 
			return false;
	}
	return true;
}

void ShowNQueen()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i] == j) cout << 'X';
			else cout << 'O';
		}
		cout << endl;
	}
	cout << endl;
}

void NQueen(int level) 
{
	// level == 열
	if (level == N) {
		result++;
		//ShowNQueen();
	}
	else {
		// level단의 행에서 가능한 애들 세기
		for (int i = 0; i < N; i++) {
			arr[level] = i;
			if (SetQueen(level))
				NQueen(level + 1);
		}
	}
}

int main()
{
	cin >> N;
	
	NQueen(0);

	cout << result;
}