[ 백준-9663번 / 브루트포스 ] N-queen

1. 문제

---

N-Queen 성공분류

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

10 초

128 MB

22421

12615

8334

55.989%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 복사

8

예제 출력 1 복사

92

 

 

 

 

 

2. 소스코드

---

1회차 - 2020/06/05

 

- 정말 간단한거 같은데, 시간초과가 났던 문제.

- Queen을 놓을 수 있는 자리인지를 어떻게 판별하냐에 따라 시간이 갈림.

- 정석은, 

1. 퀸은 무조건 row 당 1개를 놓는다.

2. column[n] 배열을 두고, 해당 column에 놓으면 체크.

 - 만약 1 col에 퀸을 놓았다면 col[1] = 1로 만들고, 나중에 해당 col을 확인하는 방식으로 O(1)만에 체크가능.

3. d1[n * 2 - 1 ] 대각선 오른쪽 위 방향,  d2[n * 2 - 1 ] 왼쪽 위 방향 두개를 두고,

 - 이건 배열 인덱스의 특징을 이용한 것.

 - 먼저 n x 2 - 1로 선언하는 건, n x n 행렬에서 대각선의 수가 n x 2 - 1 개 이기 때문.

 - 오른쪽 위 대각선 배열은 [ x + y ] 값을 인덱스로 사용함. 배열의 오른쪽 위 방향, 같은 대각선에 위치한 칸은 모두 x+y 값이 같다.

- 왼쪽 위 대각선 배열은 [ n - 1 + x - y ] 값을 인덱스로 사용함. 배열의 왼쪽 위 방향, 같은 대각선에 위치한 칸은 모두 x-y 값이 같다. 그렇지만 그대로 사용하면 음수값을 인덱스로 사용해야하는데, 배열의 인덱스는 음수값이 없으므로 n - 1을 base 값으로 두는 것.

 

이런 식으로 놓을 수 있는 지, 없는 지를 O(1)만에 확인 할 수 있어야 시간초과를 피할 수 있다.

 

#include <cstdio>
#define MAX 15

int ans, n;
int col[MAX];
int d1[MAX * 2 - 1];
int d2[MAX * 2 - 1];

void solve(int x){

	if (x == n) {
		ans++;
		return;
	}

	for (int y = 0; y < n; y++){

		if (col[y] or d1[x + y] or d2[n - 1 + (x - y)]) 
			continue;

		col[y] = d1[x + y] = d2[n - 1 + (x - y)] = 1;
		solve(x + 1);
		col[y] = d1[x + y] = d2[n - 1 + (x - y)] = 0;
	}
	return;
}
int main(){
	
	scanf("%d", &n);
	solve(0);
	printf("%d\n", ans);
	return 0;
}