[백준 9663/c++] N-Queen

백트래킹 심화 문제.

푸는 방법은 2가지가 자주 쓰인다

첫번째로, 조건을 판단할 함수를 만드는 방법

퀸은 위 아래 대각선에 영향을 주므로 퀸의 위치들을 배열에 넣은 후 

배열을 돌며 놓을 수 있는지 여부를 판단할 함수를 만들어서 푸는 방법

퀸의 위치를 나타내는 배열을 나타낼 시 배열 내 요소의 인덱스를 열로, 요소의 값을 행으로 나타내서

2차원 배열이 아닌 1차원 배열만으로 퀸의 위치를 표현 가능하다

간단하지만, 배열을 돌며 여부를 체크해야 하므로, 시간복잡도가 추가로 O(n) 가 소모된다

두번째로, 

함수대신 퀸이 영향력을 줄 수 있는 라인들을 배열로 저장해서 이전의 isused 체크처럼 사용하여

퀸을 놓을 수 있는지 체크하여 푸는 방법이다

배열의 크기를 40 으로 설정했는데, 가로가 n칸 일때 열의 인덱스화인 isused1 은 n개,

각각 서남과 동남 방향을 가리키는 대각선의 인덱스화인 isused2, isused3 의 경우 2n -1 개씩 하면

되지만, 넉넉하게 여유를 주는 것이 배열 사용의 미덕? 이므로 29가 아닌 40으로 잡게 되었다

배열을 돌지 않고, 배열의 값만으로 확인하므로 시간복잡도는 O(1)으로 첫번째보다 개선가능하다

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

9663번: N-Queen

// 첫번째 방법 : 다른 퀸의 영향을 받는지 확인하는 함수를 만들기

#include <bits/stdc++.h>
using namespace std;

int n;
int cnt = 0;
// board 배열의 인덱스는 row_idx, 요소의 값은 i 로 보면 1차원 배열만으로 가능
int board[15];

// 다음 행에 퀸을 둘 수 있는지 체크
bool isusable(int row_idx) {
	for (int i = 0; i < row_idx; i++)
	{
    		// 열이 같거나, 행의 차이가 열의 차이와 같을때 퀸을 둘 수 없다
		if (board[row_idx] == board[i] || row_idx - i == abs(board[row_idx] - board[i]))
		{
			return false;
		}
	}
	return true;
}

void bt(int row_idx) {
	if (row_idx == n)
	{
    	// 행마다 퀸을 모두 놓아 n번째 행까지 퀸을 놓았다면 경우의 수 +1
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++)
	{
    	// 퀸을 row_idx 번째 행의 열의 값이 i 인 곳에 둔다 
		board[row_idx] = i;
        // 다음 행에 퀸을 둘 수 있는가? 체크, 둘 수 있으면 재귀로 묻기
		if (isusable(row_idx))
		{
			bt(row_idx + 1);
		}
	}
}

int main(){
	
	cin >> n;
	bt(0);	
	cout << cnt;
	
	return 0;
}

---

// 두번째 방법 : 다른 퀸에 영향 받는지 확인하기 위해 배열들을 추가해서 확인

#include <bits/stdc++.h>
using namespace std;

int n;
int cnt = 0;
bool isused1[40];
bool isused2[40]; // 서남 방향 대각선
bool isused3[40]; // 동남 방향 대각선

void bt(int k) {
	// 모든 행에 퀸을 넣어 진행하여 n번째 줄까지 닿았다면 경우의 수 +1
	if (k == n)
	{
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++)
	{
    	// 다른 퀸의 영향을 받는 위치인지 체크, 그렇다면 continue
		if (isused1[i] || isused2[k + i] || isused3[k - i + n - 1])
		{
			continue;
		}
        // 다른 퀸의 영향을 받는 위치가 아니라면 사용하여 그 영향을 배열에 적용, 재귀로 다음행 확인
		isused1[i] = 1;
		isused2[k + i] = 1;
		isused3[k - i + n - 1] = 1;
		bt(k + 1);
		isused1[i] = 0;
		isused2[k + i] = 0;
		isused3[k - i + n - 1] = 0;
	}
}

int main(){
		
	cin >> n;
	bt(0);
	cout << cnt;
	
	return 0;
}