백준 알고리즘 9663 (N-Queen) - C++, Python

[문제] 백준 알고리즘 9663 (N-Queen)

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

9663번: N-Queen

 

N x N 맵에 퀸 N개를 서로 공격할 수 없게 배치하는 문제이다.

백트래킹을 이용한 문제이다.

 

[문제 해결 (정답)]

> https://rebas.kr/761 이 분이 설명해놓은 답이 가장 깔끔하다.

BOJ 9663 · N-Queen

직선 위, 대각선 양쪽 방향을 의미하는 배열을 따로 잡아서 해결하심.  

 

[문제 해결 (처음 나의 답)]

맵 자체로 접근을 해서, 한 줄 먼저 체크한다. 체크는 현재 위치보다 위쪽만 검사하면 된다.

직선 위 또는 왼쪽 대각선 또는 오른쪽 대각선을 검사한다.

시도해보며 된다고 판단되면 깊이를 추가하여 재귀시킨다.

안되면 백트래킹하고, 끝까지 간 경우를 누적하여 출력한다.

 

이 방법은 원론적이지만 시간이 조금 더 오래 걸리고,

N = 12 이상에선 답이 다른데, 백준에서는 통과됐다(????)

 

[C++ (정답)]

#include <cstdio>
using namespace std;
int n, ans = 0;
bool a[14], b[27], c[27];

void solve_dfs(int i) {
	if (i == n) {
		ans++;
		return;
	}
	for (int j = 0; j < n; j++) {
		if (!a[j] && !b[i + j] && !c[i - j + n - 1]) {
			a[j] = b[i + j] = c[i - j + n - 1] = true;
			solve_dfs(i + 1);
			a[j] = b[i + j] = c[i - j + n - 1] = false;
		}
	}
}

int main() {
	scanf("%d", &n);
	solve_dfs(0);
	printf("%d\n", ans);
	return 0;
}

 

[C++ (나의 답)]

#include <cstdio>
#include <cstring>
using namespace std;
int n, cnt = 0;
bool map[27][27];

bool check(int y, int x) {
	for (int i = 0; i <= y; i++) { // 위쪽 조사
		if (map[i][x] || map[y - i][x - i] || map[y - i][x + i]) {
			// 직선 위 또는 왼쪽 대각선 또는 오른쪽 대각선
			return false;
		}
	}
	return true;
}

void solve_dfs(int y) {
	if (y == n) {
		cnt++;
		return;
	}
	for (int x = 0; x < n; x++) {
		if (check(y, x)) {
			map[y][x] = 1; // 시도
			solve_dfs(y + 1); // 다음줄 진행해봄
			map[y][x] = 0; // 안되면 백트래킹
		}
	}
	return;
}

int main() {
	memset(map, 0, sizeof(map));
	scanf("%d", &n);
	solve_dfs(0);
	printf("%d\n", cnt);
	return 0;
}

 

[Python (정답)]

import sys
n, ans = int(sys.stdin.readline()), 0
# 직선 위, + 대각선, - 대각선
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

def solve_dfs(i):
    global ans
    if i == n:
        ans += 1
        return
    for j in range(n):
        if (not a[j] and not b[i+j] and not c[i-j+n-1]) :
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve_dfs(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False

solve_dfs(0)
print(ans)