[BOJ] 백준 9663번 N-Queen C++

문제

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

9663번: N-Queen

풀이

대표적인 백트래킹 문제인 N-Queen이다.

이 문제는 바킹독님의 영상을 참고하여 풀 수 있었다.

이제 문제를 풀어보자.

cur은 행을 의미하고 for문 안의 i는 열을 의미하며 i를 0부터 N - 1까지 모두 돌며 퀸을 배치한다.

0부터 N - 1까지 열을 for문으로 도는 이유는 서로 공격할 수 없게 퀸을 배치하기 위해서는 모든 열에 대해 퀸을 배치해주어야 하기 때문이다.

이때 퀸의 배치에 따라 퀸이 공격할 수 있는 부분을 총 3개의 isused 배열을 사용하여 처리해주었다

i) 퀸은 같은 열의 퀸에 대하여 공격할 수 있으므로 i에 대해 방문처리를 해주었다.

ii) 퀸은 왼쪽 하단에서 오른쪽 상단으로 가는 대각선 방향에 대해 공격을 할 수 있으므로 cur + i에 대해 방문처리를 해주었다.

iii) 퀸은 오른쪽 하단에서 왼쪽 상단으로 가는 대각선 방향에 대해 공격을 할 수 있으므로 cur - i에 대해 방문처리를 해주었다. 코드에서 cur - i + n으로 처리한 이유는 cur - i가 음수가 될 수 있기 때문에 이를 방지한 것이다.

위 조건들을 바탕으로 백트래킹을 돌며 n개의 퀸이 배치가 되면 cnt를 증가시키고 최종적으로 cnt를 출력하고 프로그램을 종료시켜주었다.

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

int n, cnt;
int isused1[40];
int isused2[40];
int isused3[40];

void func(int cur)
{
	if (cur == n)
	{
		cnt++;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (isused1[i] || isused2[cur + i] || isused3[cur - i + n])
		{
			continue;
		}

		isused1[i] = 1;
		isused2[cur + i] = 1;
		isused3[cur - i + n] = 1;
		func(cur + 1);
		isused1[i] = 0;
		isused2[cur + i] = 0;
		isused3[cur - i + n] = 0;
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	func(0);
	cout << cnt;
}