[BOJ] 백준 9663 N-Queen

링크

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

풀이

 #include <iostream>
using namespace std;
bool isused1[40]; //해당 인덱스 열에 대해 사용 여부를 표시. 인덱스 [y]
bool isused2[40]; //좌측 하단과 우측 상단을 잇는 대각선에 대해 사용 표시 -> 인덱스[x + y]
bool isused3[40]; //좌측 상단과 우측 하단을 잇는 대각선에 대해 사용 표시 -> 인덱스[x-y+n-1]
int cnt, n;

void func(int cur) { 
	if (cur == n) { // func(n)이 호출되면 퀸 n개 놓는데 성공했다는 의미이니 cnt를 1증가시킨다. 
		cnt++;
		return;
	}
	for (int y = 0; y < n; y++) { // cur이 x축을 의미하는구나 
		if (!isused1[y] && !isused2[cur+y] && !isused3[cur-y+n-1]) {
			isused1[y] = true; 
			isused2[cur + y] = true;
			isused3[cur - y + n - 1] = true;
			func(cur + 1);
			isused1[y] = false;
			isused2[cur + y] = false;
			isused3[cur - y + n - 1] = false;
		}
		
	}

}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	func(0);
	cout << cnt; 
}

설명

📌 기본적은 각 행에 퀸이 하나씩 두게 된다.

각 경우의 수에 대해 모두 방문하며 D행에 퀸을 놓았다면 퀸을 4개 놓는데 성공했다는 의미다.
기본틀 : func(0)을 호출해 0번째 행에 퀸을 놓고 func(1)을 호출하고 이렇게 진행하다가 func(n)이 호출되면 퀸 n개 놓는데 성공했다는 의미이니 cnt를 1증가시킨다.
👨🏻‍🏫 각 행에 퀸을 한개씩만 놓으니까 한 행에 퀸이 2개인지는 생각할 필요가 없는데 열과 대각선에 열과 대각선에 대해서는 생각을 해야된다.

• 같은 열에 대한 조건 : y좌표가 같으면 같은 열이다.

• 좌측 하단과 우측 상단을 잇는 대각선 : x+y가 같으면 같은 대각선에 위치해있다.

• 좌측 상단과 우측 하단을 잇는 대각선 : x-y가 같으면 같은 대각선에 위치해있다.

  
  놓은 모든 퀸에 대해 대각선 혹은 열에서 만나는 것이 있는지를 확인하려고 한다면 그 과정에서 O(N)이 추가로 필요하게 되는데 각 대각선과 열의 점유 상태를 나타낼 isused 변수를 두면 시간이 절약된다.

• isused1은 열에 대응되는 값으로, (x,y)에 퀸이 있으면 isused1[y]를 true로 만든다.

• 좌측하단과 우측상단 대각선 : isused2[x+y]를 true로 만든다.

• 좌측상단과 우측하단 대각선 : isused2[x-y+n-1]를 true로 만든다. -> 인덱스를 음수로 보내지 않게 하기 위해서 n-1를 추가했다.