백준 9663번 N-Queen C++ 백트래킹, 브루트포스 알고리즘

리뷰

SSAFY 백트래킹 시간에 배워서 풀었다. 싸피 짱!

 

문제 풀이

1. DAT 배열을 총 세개 만들어 준다. col 기준, 우하향, 좌하향 대각선에 방문 체크를 하기 위함
2. 우하향, 좌하향 DAT의 index로 전달해 줄 값을 저장할 2차 배열 2개를 만들어 준다.
3. 우하향 배열은 우하향 대각선의 값이 같게, 좌하향 배열은 좌하향 대각선의 값이 같게 만들어준다. 값은 DAT의 범위 내에 있고, 각 대각선과 값이 겹치지 않는다면 상관 없다.
4. row를 매개변수로 0부터 백트래킹을 시작한다. 만약 row가 n과 동일하다면 배치가 가능한 것이다. cnt를 1 더해준다.
5. for문을 시작하고 0부터 n까지 순회를 돈다. 위에서 말했듯 행은 현재 재귀의 row로 받고 있다.
6. 현재 열에 놓을 수 있다면 (판별 조건을 통과했다면) 모든 행의 현재 열, 현재 열로부터 좌/우하향 대각선에 방문처리를 하고 다음 행으로 재귀를 호출해준다.
7. 이후 방문처리 했던 내용을 다시 철회한다.
8. 백트래킹이 완료된 후 cnt에 저장된 값을 출력한다.

 

참고 사항

우하향 하는 DAT배열은 다음과 같다. 예제는 모두 N의 최대값인 14로 들겠다.

// int rd[15][15]
14 13 12 11 10 9 8 7 6 5 4 3 2 1
15 14 13 12 11 10 9 8 7 6 5 4 3 2
16 15 14 13 12 11 10 9 8 7 6 5 4 3
17 16 15 14 13 12 11 10 9 8 7 6 5 4
18 17 16 15 14 13 12 11 10 9 8 7 6 5
19 18 17 16 15 14 13 12 11 10 9 8 7 6
20 19 18 17 16 15 14 13 12 11 10 9 8 7
21 20 19 18 17 16 15 14 13 12 11 10 9 8
22 21 20 19 18 17 16 15 14 13 12 11 10 9
23 22 21 20 19 18 17 16 15 14 13 12 11 10
24 23 22 21 20 19 18 17 16 15 14 13 12 11
25 24 23 22 21 20 19 18 17 16 15 14 13 12
26 25 24 23 22 21 20 19 18 17 16 15 14 13
27 26 25 24 23 22 21 20 19 18 17 16 15 14

 

좌하향 하는 DAT 배열이다.

// int ld[15][15]
0 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 4 5 6 7 8 9 10 11 12 13 14 15 16
4 5 6 7 8 9 10 11 12 13 14 15 16 17
5 6 7 8 9 10 11 12 13 14 15 16 17 18
6 7 8 9 10 11 12 13 14 15 16 17 18 19
7 8 9 10 11 12 13 14 15 16 17 18 19 20
8 9 10 11 12 13 14 15 16 17 18 19 20 21
9 10 11 12 13 14 15 16 17 18 19 20 21 22
10 11 12 13 14 15 16 17 18 19 20 21 22 23
11 12 13 14 15 16 17 18 19 20 21 22 23 24
12 13 14 15 16 17 18 19 20 21 22 23 24 25
13 14 15 16 17 18 19 20 21 22 23 24 25 26

 

보면 알겠지만 우하향 배열의 최대값은 2N-1, 좌하향 배열의 최대값은 2(N-1)로 대각선 DAT 배열은 범위를 col DAT 배열보다 크게 설정해 주어야 한다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int n, cnt;
int vcol[15];
int vrd[30];
int vld[30];
int rd[15][15];
int ld[15][15];

void bt(int row) {
	if (row >= n) {
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (vcol[i]) continue;
		if (vrd[rd[row][i]]) continue;
		if (vld[ld[row][i]]) continue;
		vcol[i] = 1;
		vrd[rd[row][i]] = 1;
		vld[ld[row][i]] = 1;
		bt(row + 1);
		vcol[i] = 0;
		vrd[rd[row][i]] = 0;
		vld[ld[row][i]] = 0;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			rd[i][j] = i - j + n;
			ld[i][j] = i + j;
		}
	}
	bt(0);
	cout << cnt;
}