[백준 BOJ][C++]9663번 N-Queens 풀이: DFS & 백트래킹

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 초기 구현에서는 2차원 배열을 사용하여 퀸의 위치에서 동, 서, 남, 북, 대각선 방향의 모든 칸을 해당 열의 번호로 설정하고 dfs의 재귀호출이 끝나면 다시 이 칸들을 0으로 설정하여 구현하였습니다. 

 

 맞았습니다! 가 떴지만 실행 시간이 9초 정도가 나와서 보완하고자 구글링을 통해 보다 좋은 성능을 가진 코드를 구현하였습니다. 

 

 col[x] = x열의 Queen이 위치한 행, y를 의미합니다. 

 

 dfs(x)는 x열, i번째(1<=i<=n) 행에 Queen이 위치할 수 있다면 dfs(x+1)을 호출합니다.

 

 이때의 재귀호출을 할 조건은 1열부터 x-1열까지 x열의 Queen이 올 위치와 동서남북대각선으로 겹치지 않는지 확인해야 합니다.

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

int n;
int ans;
int col[15];

bool check(int x) {
	for (int i = 1; i < x; i++) {
		if ((col[x] == col[i]) || (abs(col[x] - col[i]) == abs(x - i)))
			return false;
	}
	return true;
}

void dfs(int x) {
	if (x == n + 1) {
		ans++;
		return;
	}

	for (int i = 1; i <= n; i++) {
		col[x] = i;
		if (check(x))
			dfs(x + 1);
	}

}

int main(void) {

	cin >> n;

	dfs(1);
	cout << ans;

	return 0;
}

 

 

[초기 코드]

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

int n;
int ans;
int map[15][15];

bool is_digonal(int px, int py, int cx, int cy) {
	int dx = abs(px - cx);
	int dy = abs(py - cy);

	if (dx == dy)
		return true;
	else
		return false;
}

void set_attack(int x, int y, int col, int set) {

	for (int i = 1; i <= n; i++) {
		for (int j = x; j <= n; j++) {
			if (i == y || j == x || is_digonal(x, y, j, i)) {
				if (map[i][j] == col)
					map[i][j] = set;
			}
		}
	}
}

void dfs(int col) {

	if (col == n + 1) {
		ans++;
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (map[i][col] == 0) {
			set_attack(col, i, 0, col);
			map[i][col] = -1;
			dfs(col + 1);
			set_attack(col, i, col, 0);
			map[i][col] = 0;
		}
	}
}

int main(void) {

	cin >> n;

	dfs(1);
	cout << ans;

	return 0;
}