[C++] 9663 : N-Queen

골드 Ⅴ

 

#include <iostream>
#include <cstdlib>

using namespace std;

int n;
int cnt = 0;
int map_c[15];

int promising(int cidx) {

	for (int i = 0; i < cidx; i++) {
		if (map_c[i] == map_c[cidx] || (cidx - i) == abs(map_c[i] - map_c[cidx]))
			return 0;
	}
	
	return 1;
}

void nqueen(int cidx) {

	if (cidx == n) {
		cnt++;
		return;
	}

	for (int ridx = 0; ridx < n; ridx++) {
		map_c[cidx] = ridx;
		if (promising(cidx)) nqueen(cidx + 1);
	}
}

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

 

백트래킹 문제!

드디어 알고리즘 하나 더 하려고 발을 딛었다.. 맨날 DFS만 주구장창 풀었는데ㅋㅋ..

 

주의깊게 봐야할 점

① 이차원 배열을 사용하지 않고 일차원 배열로 이차원 배열을 나타냄

② 백트래킹의 "다시 뒤로 돌아가는" 부분은 for문 + 재귀 함수를 이용함으로써 자동적으로 해결 됨

③ cidx를 n까지 봐줌 -> 실제 체스판에서는 n+1 번째 항까지 봐주는 것 -> n번째 항도 똑같이 백트래킹 해주기 위함이다

④dy/dx == m 이고, 체스판에서 대각선에 위치한 것은 m = ±1 인 것이므로 dy/dx = ±1, 즉 dy = abs(dx) 해주면 된다

 

 

① 이차원 배열을 사용하지 않고 일차원 배열로 이차원 배열을 나타냄

 

예를들어, n=4일 때

map_c[0] = 1, map_c[1] = 3, map_c[2] = 0, map_c[3] = 2

로 나타내어 주면

(r, c) -> (0, 1), (1, 3), (2, 0), (3, 2) 로 나타내어 준 것과 같다!!

배열의 인덱스를 활용하여

배열의 차수 줄여주기!(2차원 -> 1차원)

응용하면 n차원 -> n-1차원 으로도 쓸 수 있지 않을까?

아무튼 배열의 인덱스는 여기저기 쓸 데가 많다

 

② 백트래킹의 "다시 뒤로 돌아가는" 부분은 for문 + 재귀 함수를 이용함으로써 자동적으로 해결 됨

 

예를들어 nqueen 의 이 for문에서, ridx = 2 라고 해보자

for (int ridx = 0; ridx < n; ridx++) {
	map_c[cidx] = ridx;
	if (promising(cidx)) nqueen(cidx + 1);
}

promising(cidx) (map_c 의 cidx에 ridx를 넣은 것이 타당한가? 를 확인하는 함수) 를 거치고

nqueen(cidx + 1) 을 하다보면, 언젠가 promising 결과값이 0이 되든 cidx가 n까지 가든 해서 ridx = 2일 때 if 문이 끝날 것이다

그럼 자동으로 ridx = 3 로 넘어가므로 백트래킹을 해주는 셈이 된다!

 

 

추가로

이건 내가 이해한건데.. 백트래킹은 브루트포스 -> 근데 가지치기(볼 필요 없는 애들은 안 봄)가 추가 된 인 것 같다

 

이걸 생각하면 ②의 이해가 더 쉽게 되는 것 같다

 

그럼 앞으로도 백트래킹 문제를 훨씬 많이 풀어보길 바라며..

끝