백준 9663 N-Queen - C언어 DFS

NxN 체스판에 N개의 퀸을 두는 문제이다.

DFS에서 가장 유명한 문제가 아닐까싶다.

DFS가 유용하다는 것을 보이기 위해서 이거만한 문제가 없는 것 같다.

왜냐하면 원래 체스판은 8x8에 불과하기 때문에 손으로도 금방 (92번만하면) 모든 경우를 다 찾을 수 있지만

만약 체스판이 14칸까지 늘어난다면 한참(36만++) 걸릴 것이기 때문이다.

 

이 문제는 DFS로 접근하되 2가지 최적화를 사용했다.

 

1. 순수하게 문제 그대로 DFS를 사용하되 퀸을 놔도 되는지 체크하는 함수를 최적화

2. 체스판을 그룹화하여 사용한 그룹을 체크해놓는 look up table 생성

 

퀸을 놔둔 자리는 Chess[][]에 1로 표시한다.

체스판의 범위는 0부터 N-1 까지로 입력받는다.

---

1번 방식부터 사용해본다.

int check(int y, int x) {
	//dfs를 통해 한 줄에 하나씩만 두므로 세로,대각선만 확인한다.
	//세로 확인 (y까지만 확인해도 될듯)
	for (int i = 0; i < N; i++) {
		if (Chess[i][x] == 1)
			return 0;
	}
	//대각선확인 기존에 둔거만 신경쓰면 되므로 위쪽만 검사(밑에 줄은 아직 퀸을 두지 않은 상태)
	int i = 1;
	for (;;) {
		if (y - i < 0 || x - i < 0) break;//범위 초과
		if (Chess[y - i][x - i] == 1) return 0;
		i++;
	}
	i = 1;
	for (;;) {
		if (y - i < 0 || x + i >= N) break;//범위초과
		if (Chess[y - i][x + i] == 1) return 0;
		i++;
	}
	return 1;//놔도 문제 없을 경우

int DFS(int y, int x, int num) {
	if (num == N) {
		cnt++;
		return 0;
	}
	for (int i = 0; i < N; i++) {
		if (check(y + 1, i)) {
			Chess[y + 1][i] = 1;
			DFS(y + 1, i, num + 1);
			Chess[y + 1][i] = 0;
		}
	}

}

 

 

체크함수는 말그대로 퀸을 놔도 되는지 확인하는 함수이다.

DFS는 좌표와 퀸을 놓은 횟수를 받아서 확인한다. 

만약 N개를 모두 놨다면 cnt에 기록하고 종료한다.

 

가로줄을 기준으로 생각한다면, 한 줄에는 하나의 퀸만 놓을 수 있기 때문에

자리를 정했다면 다음 퀸은 반드시 그 밑에 줄에 존재할 수 밖에 없다. (비둘기집, N개의 집에 N개의 비둘기를 중복 없이 넣어야하므로)

그러므로 DFS를 수행할 때 y+1을 파라미터로 주어 가로줄은 생각하지 않는다.

 

여기서 수행시간에 가장 큰 영향을 주는 것은 Check 함수가 된다.

check함수는 퀸의 행동 반경에 따라 모든 체스판을 검사한다.

내가 놓을 자리를 기준으로 다른 퀸이 올 수 있는지를 판단하는데,

앞서 말한 것처럼 가로는 신경쓰지 않아도 되므로 세로, 대각선2개를 검사한다.

 

대각선 2개를 검사할 때, 아직 밑에 줄엔 아무 퀸이 놓아지지 않았기 때문에 위쪽만 검사하는 것으로 

최적화시켰다.

 

---

2번은 체스판의 가로, 세로, 대각선을 그룹화 시켜서 한 번에 확인할 수 있도록 룩업 테이블을 만드는 것이다.

//세로 대각선 대각선
//우하향 대각선은 x-y +N-1 으로 묶임
//우상향대각선은 y+x 로 묶임
int check1[MAXN];
int check2[MAXN * 2];
int check3[MAXN * 2];

int sol(int row,int queen) {
	if (queen == N) {
		cnt++; return 0;
	}
	for (int i = 0; i < N; i++) {
		if (check1[i]) continue;
		if (check2[i - row + N-1])continue;
		if (check3[i + row]) continue;
        //
		check1[i] = 1;
		check2[i - row + N - 1] = 1;
		check3[i + row] = 1;
        //dfs 진입
		sol(row + 1, queen + 1);
        //dfs 탈출
		check1[i] = 0;
		check2[i - row + N - 1] = 0;
		check3[i + row] = 0;
	}
	return 0;
}

 

 

 

check1 은 세로, check2 는 우하향 대각선, check3 는 우상향 대각선을 뜻한다.

그룹의 인덱스는 다음과 그림과 같이 결정한다.

해당 좌표가 어디 그룹에 속하는지 인덱스를 그룹별로 각각 구한다.

(세로는 i, 우하향 대각선은 N-1-y+x, 우상향 대각선은 y+x)

그리고 이미 사용된 그룹인지를 판단하고 사용되지 않은 그룹에 속할때만 dfs로 밑에줄로 넘어간다.

 

하나하나 확인한 경우보다 거의 4배 빨라졌다.

물론 서버라서 정확하진 않을 수도 있지만, 어쨌든 확연히 빨라졌다.

체스판 N*N을 따로 저장히자 않아서 메모리 크기도 비슷하거나 작아진다.

 

새로운 시각으로 체스판을 볼 수 있는 기회였던 것 같다.

 

전체코드

#include <stdio.h>

int N;
int cnt;
int Chess[13][13];


void InputData(void) {
	scanf("%d", &N);
}
//1번방식
//int check(int y, int x) {
//	//가로는 어차피 한개씩둠
//	//세로 확인
//	for (int i = 0; i < N; i++) {
//		if (Chess[i][x] == 1)
//			return 0;
//	}
//	//대각선확인 기존에 둔거만 신경쓰면 되므로 위쪽만 검사
//	int i = 1;
//	for (;;) {
//		if (y - i < 0 || x - i < 0) break;
//		if (Chess[y - i][x - i] == 1) return 0;
//		i++;
//	}
//	i = 1;
//	for (;;) {
//		if (y - i < 0 || x + i >= N) break;
//		if (Chess[y - i][x + i] == 1) return 0;
//		i++;
//	}
//	return 1;
//}
//
//int DFS(int y, int x, int num) {
//	if (num == N) {
//		cnt++;
//		return 0;
//	}
//	for (int i = 0; i < N; i++) {
//		if (check(y + 1, i)) {
//			Chess[y + 1][i] = 1;
//			DFS(y + 1, i, num + 1);
//			Chess[y + 1][i] = 0;
//		}
//	}
//
//}
//2번방식
#define MAXN 13
int sol = 0;
int check1[MAXN];//세로줄 [c]
int check2[MAXN * 2];//좌상단 [N-1+c-r]
int check3[MAXN * 2];//우상단 [r+c]
void DFS(int r) {
	if (r >= N) {
		sol++; return;
	}
	for (int c = 0; c < N; c++) {
		if (check1[c]) continue;
		if (check2[N - 1 + c - r]) continue;
		if (check3[r + c]) continue;
		check1[c] = check2[N - 1 + c - r] = check3[r + c] = 1;//표시
		DFS(r + 1);
		check1[c] = check2[N - 1 + c - r] = check3[r + c] = 0;//표시제거
	}
}

int main(void)
{
	int ans = 0;

	InputData();// 입력받는 부분

	// 여기서부터 작성
	DFS(0);
	ans = sol;
	printf("%d\n", ans);// 출력하는 부분

	return 0;
}