19) 백준 9663 - N-Queen

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

---

몇 주 전에 하려다가 머리가 안 굴러가서 포기했던 문제.

#include <iostream>

using namespace std;

int N;
int answer;

int check(int chess[15][15], int x, int y) {
	int tmp_X = x-1;
	int min = y-x;
	int sum = x+y;
	
	while(tmp_X >= 0) {
		if(min + tmp_X >= 0) {
			if(chess[tmp_X][min + tmp_X] == 1) return 0;
		}
		if(sum - tmp_X < N) {
			if(chess[tmp_X][sum - tmp_X] == 1) return 0;
		}
		if(chess[tmp_X][y] == 1) return 0;
		
		tmp_X--;
	}
	
	return 1;
}

void bf(int cnt, int chess[15][15], int x) {
	if(cnt == N) {
		answer++;
		return;
	}
	for(int j = 0; j < N; j++) {
		int ck = check(chess, x, j);
		if(check(chess, x, j) == 1) {
			chess[x][j] = 1;
			bf(cnt+1, chess, x+1);
			chess[x][j] = 0;
		}
	}
}


int main(void) {
	int chess[15][15] = {0, };
	answer = 0;
	
	cin >> N;
	
	int cnt = 0;
	bf(cnt, chess, 0);
	
	cout << answer << endl;
	
}

2차 배열을 사용했다. 쉬운 듯 어려웠던 문제.

 

백트래킹 문제로  Queen을 그냥 하나하나 옮겨가면서 놓으면서 체크하면 끝난다.

 

처음 check 함수에서 놓는 체스말 아래 행까지 체크하려고 하고, bf 함수에서 for문을 행과 열 전부 돌아가며 체크하려고 했는데 시간초과가 걸렸다.

 

여기서 아이디어는

1. 한 행에 놓으면 그 행은 더 이상 놓지 못한다. 다르게 생각하면 N×N 보드판에 N개의 Queen체스 말을 놓기 위해선 한 행에 하나씩 모든 행에 각각 하나씩 놓아야 한다.

2. 체스판 위쪽부터 체스말을 놓으므로 새로 놓는 행을 포함하여 그 아래 행은 체크할 필요가 전혀 없다.

 

sum 은 행과 열의 합, min은 행과 열의 차 이 둘을 이용해서 대각선을 계산해 줬는데 이 방법을 사용해서 굳이 2차로 안 하고 1차 배열을 사용해서도 문제를 풀 수 있었다.

 

---

< 초반 오답 코드 >

#include <iostream>

using namespace std;

int N;
int answer;

int check(int chess[15][15], int x, int y) {
	int tmp_X = x;
	int tmp_Y = y;
	while(tmp_X >= 0 && tmp_Y >= 0) {
		if(chess[tmp_X][tmp_Y] == 1) {
			return 0;
		}
		else {
			tmp_X--;
			tmp_Y--;
		}
	}
	
	tmp_X = x;
	tmp_Y = y;
	while(tmp_X < N && tmp_Y < N) {
		if(chess[tmp_X][tmp_Y] == 1) {
			return 0;
		}
		else {
			tmp_X++;
			tmp_Y++;
		}
	}
	
	tmp_X = x;
	tmp_Y = y;
	while(tmp_X < N && tmp_Y >= 0) {
		if(chess[tmp_X][tmp_Y] == 1) {
			return 0;
		}
		else {
			tmp_X++;
			tmp_Y--;
		}
	}
	
	tmp_X = x;
	tmp_Y = y;
	while(tmp_X >= 0 && tmp_Y < N) {
		if(chess[tmp_X][tmp_Y] == 1) {
			return 0;
		}
		else {
			tmp_X--;
			tmp_Y++;
		}
	}
	
	for(int i = 0; i < N; i++) {
		if(chess[i][y] == 1) {
			return 0;
		}
	}
	return 1;
}

void bf(int cnt, int chess[15][15], int x) {
	if(cnt == N) {
		answer++;
		return;
	}
	
	for(int i = x; i < N; i++) {
		for(int j = 0; j < N; j++) {
			int ck = check(chess, i, j);
			if(check(chess, i, j) == 1) {
				chess[i][j] = 1;
				bf(cnt+1, chess, i+1);
				chess[i][j] = 0;
			}
		}
	}
}


int main(void) {
	int chess[15][15] = {0, };
	answer = 0;
	
	cin >> N;
	
	int cnt = 0;
	bf(cnt, chess, 0);
	
	cout << answer << endl;
	
}

확실히 초반에 비해서 시간이 반으로 줄고 이중 for문을 사용하지 않다 보니 훨씬 시간이 줄어든 것이 보였다.

check안의 함수는 억지로 꾸역꾸역 줄이려다 보니 저렇게 간단해지긴 했는데 sum, min을 따로 안 하고 오답 코드처럼 보기 쉽게 해도 통과된다