[C++/BOJ] 백준 9663 N-Queen(백트래킹)_결국 풀었다

 

 

문제는 아주 간단하다 

N이 주어질때 N*N 체스판에서 N개의 퀸을 놓는 방법의 수를 출력하면 된다.

 

 

일단 코드는  check 와 queen 함수를 사용하였다. 

#include<iostream>
using namespace std;
int col[16],cross1[30], cross2[30];//15*2-1 = 29이므로 약 30
int cnt, n ;

bool check(int r, int c) { // 놓을 수 있는 자리인가
	if (col[c] || cross1[r+c] || cross2[r-c+n-1]) return false;
	return true;
}

void queen(int row) { //row 행에 퀸 놓을 자리 찾기 
	if (row == n) {// 방법 하나 발견!
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++) {	
		if (check(row, i)) {
			col[i] =1;
			cross1[row + i] = 1;
			cross2[row - i + n - 1] = 1;
			queen(row + 1);
			col[i] = 0;
			cross1[row + i] = 0;
			cross2[row - i + n - 1] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	queen(0); // 1행에 놓을 자리 찾기
	cout << cnt;
}

 

 

 

• HOW?

행으로 for 문을 돌리면서 3개의 배열을 확인한다. 

 

 

• 3개의 배열?

행의 경우 for문을 이용해 돌리기때문에 확인할 필요없다.

확인해야할 것은 열, 우측상단으로의 대각선, 우측 하단으로의 대각선

 

왜 이것들을 확인하는가?

퀸은 같은 행, 같은 열, 같은 대각선이라면 어디든 갈 수 있다.

행은 앞서 말했듯이 for문으로 한줄씩 queen함수를 이용해 넘어가므로 상관하지말고

열은 col배열을 이용하면 되고, 대각선의 경우 우측 상단으로의 대각선, 우측 하단으로의 대각선 이 두개로 나뉜다.

 

 

 

체스판을 생각해보면 우측 상단으로의 대각선의 행 과 열의 합은 같다!

 

 

가장 왼쪽 아래 칸은 3,0 으로 합하면 3이다. 그 다음 우측 상단 대각선 칸의 행과 열은 2,1 이므로 합은 3이다. 

이렇듯 우측 상단으로의 대각선은 행과 열의 합이 같다. 

 

 

 

 

 

이것은 우측 하단으로 가는 대각선을 생각한 것이다. 

이렇든 행 - 열의 값이 동일함을 확인 할 수 있다. 

 

 

 

이 세가지를 각각 배열로 만들어 이곳에 퀸을 놓아도 되는지 아닌지 확인한다.

 

• col [16] => 열을 확인할 배열
• cross1[30] => 우측 상단으로 가는 대각선 
• cross2[30] => 우측 하단으로 가는 대각선 

 

cross 배열의 크기가 30인 이유는 표를 그려보며 개수를 세어보면 알 수 있다.

대각선의 개수는 2n-1 이기때문에 최대 n인 15을 넣고 계산하면 29이다. 그래서 배열의 크기를 30으로 놓았다.

 

 

 

 

 

• 왜 cross2 가 [row - col + n - 1] 인가 ?

 

cross2는 우측 하단으로 가는 대각선이다.

행 - 열 의 값이 동일하지만 음수의 값이 나오게 된다. 

 

배열에서 음수의 값이 나올수는 없으므로 n-1을 더해주어 가장 작은 음수를 0으로 만들어준다. 

 

그래서 cross2배열의 이용을 할 수 있는 것이다. 

 

 

 

 

nqueen 풀면서 끄적인 것들

 

 

다 이해하고 보면 그렇게 어려운 문제는 아니다.

그러나 처음 이 문제를 본 이번 년 초,  1시간 가량 문제를 풀었지만 너무 어렵고 이해가 안되서 포기했었다. 

그 후 7월 22일에 다른 사람 해설을 보고 끙끙대면서 잘 이해하지 못한 코드로 AC를 받았다.

11월 7일 이 문제를 완벽하게 이해하고 풀 수 있다.

 

 

알고리즘 문제를 풀며 조금씩 성장하는 것 같아 뿌듯하다.

 

 

 

 

참고 블로그 : 갓킹독님 백트리킹 포스팅

https://blog.encrypted.gg/945?category=773649 

 

 

 

 

 

https://coupa.ng/b95sID

삼성전자 갤럭시 버즈2 블루투스 이어폰

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."