[C/C++] 코드업(codeup) 3520번 체커 도전(N-Queen Problem)

▽문제 바로가기

https://codeup.kr/problem.php?id=3520

체커 도전 (N-Queen Problem)

---

입력

체스판의 크기 N이 입력된다( 6 <= N <= 13 )

 

출력

처음 세 줄은 가능한 해법 3가지를 출력한다. 이때 열번호가 적은 순서부터 오름차순으로 세 가지만 출력한다.

네째 줄에 가능한 퀸의 배치 개수를 출력한다.

 

문제 풀이

 

해법 가짓수와 열 번호를 오름차순으로 세 가지 출력해야 합니다. 열 번호를 출력하는 것은 완전 탐색을 순서대로 진행하면 자동으로 오름차순이 되므로 문제 되지 않습니다.

 

모든 경우의 수를 탐색해야 하는데 입력 최대가 13이므로 13^13은 백억이상의 매우 큰 수입니다.

 

따라서 완전 탐색을 하면서 불필요한 탐색을 줄여야합니다.

이 부분은 코드업 3515번 사탕 줍기 2 문제와 동일합니다.

 

▽바로가기

https://swblossom.tistory.com/63

[C/C++] 코드업(codeup) 3515번 사탕 줍기 2

 

열이 겹치는 경우와 대각선이 겹치는 경우에 탐색을 하지 않도록 판별해야 합니다. 열이 겹치는 경우는 그동안 선택한 열을 저장하면서 판별이 가능합니다. 이제 대각선으로 겹치는지 판별해야 합니다.

 

대각선의 경우 오른쪽 대각선과 왼쪽 대각선, 두 가지로 생각할 수 있습니다. 

	1	2	3	4
1	선택1
2			선택2
3		선택2의 왼쪽 대각선		선택2의 오른쪽 대각선
4	선택2의 왼쪽 대각선

1행에서 1열을 선택했고 2행에서 3열을 선택했을 경우 선택2와 대각선으로 겹치는 경우는 왼쪽 대각선과 오른쪽 대각선입니다.

 

오른쪽 대각선의 경우 선택2의 열(저장된 경로) - 선택2의 행 = 앞으로 선택할 열 - 앞으로 선택할 행 공식이 성립하면 대각선으로 겹칩니다.

ex) 선택3을 선택할 때 3 - 2 = 4 - 3 -> 오른쪽 대각선으로 겹침

 

왼쪽 대각선의 경우 선택2의 열(저장된 경로) - 앞으로 선택할 열 = 앞으로 선택할 행 - 선택2의 행 공식이 성립하면 대각선으로 겹칩니다.

ex) 선택3을 선택할 때 3 - 2 = 3 - 2 -> 왼쪽 대각선으로 겹침

ex) 선택4를 선택할 때 3 - 1 = 4 - 2 -> 왼쪽 대각선으로 겹침

 

#include <stdio.h>

using namespace std;

int n;
int cache[15] = {0,};	//경로를 저장하는 배열
int cnt = 0;	//해법가지수 카운트
int cnt2 = 0;	//경로 3가지만 저장 

//필요한 탐색인가? 
bool isPromising(int row, int col){
	for(int i=0;i<row;i++){
		if(cache[i]==col+1) return false;	//같은 열이면 
		if(cache[i]-i==col-row+1) return false;	//오른쪽 대각선으로 겹치면 
		if(cache[i]-col==row-i+1) return false;	//왼쪽 대각선으로 겹치면
	}
	return true;
}

//백트래킹
void backtracking(int row){
	
	//출력 
	if(row==n){
		cnt++; //해법수 카운트
		if(cnt2<n*3){	//3가지 출력안했으면 출력
			for(int i=0;i<n;i++){
				printf("%d ", cache[i]);
				cnt2++;
			}
			printf("\n");
		}
		return;
	}
	
	for(int i=0;i<n;i++){
		if(isPromising(row, i)){
			cache[row] = i+1;	//경로저장(1열 선택하면 1저장)
			backtracking(row+1);
		}
		else continue;
	}
}


int main(){
	
	scanf("%d", &n);
	
	backtracking(0);
	
	printf("%d", cnt);
	
	return 0;
}