[백준 C++] 9663 N-Queen - 백트래킹

9663번: N-Queen

#include <iostream>
using namespace std;

int N, Cnt;
int Col[14];

bool Check(int Index)
{
	for (int i = 0; i < Index; ++i)
	{
		if (Col[i] == Col[Index]
			|| abs(Col[Index] - Col[i]) == Index - i)
		{
			return false;
		}
	}

	return true;
}

void DFS(int Index)
{
	if (Index == N)
	{
		++Cnt;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		Col[Index] = i;
		if (Check(Index))
		{
			DFS(Index + 1);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N;
	DFS(0);
	cout << Cnt;
}

---

 

DFS & 백트래킹을 이용해서 N개의 퀸을 놓을 수 있는 모든 경우를 탐색하는 문제입니다.

주의할 점은 2차원 배열로 풀면 시간초과가 발생합니다.

 

따라서 각 열 마다 어느 행에 퀸을 배치할 것인지를 저장하는 1차원 배열로 풀어야 합니다.

깊이 우선 탐색으로 각 열 마다 놓을 수 있는 행에 퀸을 배치해가면서 모든 경우를 탐색해주면 됩니다.

 

놓을 수 있는 행을 체크하는 조건은 다음과 같습니다.

1. 다른 열의 퀸과 행이 겹치지 않아야 함: Col[i] != Col[Index]

2. 다른 열의 퀸과 대각선으로 겹치지 않아야 함: abs(Col[Index] - Col[i]) != Index - i