[BOJ]9663번: N-Queen (c++)

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

9663번: N-Queen

 

방법 1 : 2차원 배열을 만들어서 공격 가능한 지점들을 미리 제외하기

#include <iostream>
#include <vector>

using  namespace std;

int dr_x[] = {1, 1, 1};
int dr_y[] = {1, 0, -1};
int N, cnt;

// 퀸이 공격 가능한 지점의 값을 +num 하기 (좌하향, 아래, 우하향) 
void check_ways(vector<vector<int>>& check, int x, int y, int num)
{
	for (int i = 0; i < 3; ++i)
	{
		int nx = x + dr_x[i];
		int ny = y + dr_y[i];

		while (!(nx < 0 || nx >= N || ny < 0 || ny >= N))
		{
			check[nx][ny] += num;
			nx += dr_x[i];
			ny += dr_y[i];
		}
	}
}

void go(vector<vector<int>>& check, int row)
{
	// N개의 퀸 자리가 정해지면 카운팅 후 종료
	if (row == N)
	{
		++cnt;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		// 현재까지 정해진 퀸이 공격가능한 지점이 아니면
		if (check[row][i] == 0)
		{
			// 현재지점으로부터 퀸이 공격가능한 모든 지점에 +1
			check_ways(check, row, i, 1);
			
			// 다음행의 퀸을 정하기 위해 go함수 재귀호출
			go(check, row + 1);
			
			// 현재지점으로부터 퀸이 공격가능한 모든 지점에 -1
			check_ways(check, row, i, -1);
		}
	}
}

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

	// 입력
	cin >> N;
	vector<vector<int>> check(N, vector<int>(N));

	// N개 퀸이 서로 공격할 수 없도록 하는 경우의 수 구하기
	go(check, 0);

	// 출력
	cout << cnt;

	return 0;
}

 

방법 2: 열, 대각선 배열을 만들어서 이미 차지된 열/대각선은 제외하기

#include <iostream>

using  namespace std;

const int MAX = 15;
bool ck_col[MAX];
bool ck_left_diag[MAX * 2];
bool ck_right_diag[MAX * 2];
int N, cnt;

bool possible(int row, int col)
{
	if (ck_col[col] || ck_left_diag[row + col] || ck_right_diag[row - col + N])
	{
		return false;
	}
	return true;
}

void change_flag(int row, int col, bool flag)
{
	ck_col[col] = flag;
	ck_left_diag[row + col] = flag;
	ck_right_diag[row - col + N] = flag;
}

void go(int row)
{
	// N개의 퀸 자리가 정해지면 카운팅 후 종료
	if (row == N)
	{
		++cnt;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		// 현재까지 정해진 퀸이 공격할 수 없는 위치이면
		if(possible(row, i))
		{
			// (row, i)의 열, 좌하향 대각선, 우하향 대각선 벡터 true 플래그 체크하기
			change_flag(row, i, true);
			
			// 다음행의 퀸을 정하기 위해 go함수 재귀호출
			go(row + 1);
			
			// (row, i)의 열, 좌하향 대각선, 우하향 대각선 벡터 false 플래그 체크하기
			change_flag(row, i, false);
		}
	}
}

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

	// 입력
	cin >> N;

	// N개 퀸이 서로 공격할 수 없도록 하는 경우의 수 구하기
	go(0);

	// 출력
	cout << cnt;

	return 0;
}

 

 

둘다 백트랙킹 방식이고 시간복잡도도 O(N ^ N)이다.

코테에서 갑자기 등장한다면 나는 방법1이 먼저 생각날 것 같다