백준[9663] N-Queen

문제 설명

문제 링크

http://icpc.me/9663

풀이

백트레킹을 이용하여 풀이할 수 있다,

백트레킹을 이용하면서 약간의 테크닉이 필요하다.

N * N 크기의 배열에 좌표가 있는지 true/false로 저장을 해놓으면 퀸이 놓을 수 있는지 확인하는데 시간이 많이 든다.

한 행에는 하나의 퀸만 놓일 수 있다는 점을 이용하여 크기가 N인 배열만을 이용하여 퀸을 놓을 수 있는지 여부를 확인할 수 있다.

visited 배열은 visited[2] = 1이라고 하면 (1, 2)의 점에 퀸이 놓아져 있다는 의미로 사용할 수 있다.

 0 ~ n -1 행순으로 채운다고 할떄, 현재 행 x를 채울 때 같은 열에 있는지 확인하는 방법은 0 ~ x-1 행의 값 중 x행에 채울 값과 동일한 값이 있는지 체크하면 된다. 대각선에 놓여있는지 확인할 때에는 점 c1, c2의 가울기가  +1 or -1이 되면 안 된다.

코드

#include <cstdio>
#include <cmath>

int visited[16], ans, n;

bool possible(int cur) {
    for (int i = 0; i < cur; i++) {
        if (visited[i] == visited[cur] || abs(visited[i] - visited[cur]) == cur - i) return false;
    }
    return true;
}

void solve(int cur) {
    if (cur == n) {
        ans++;
        return;
    }
    for (int i = 0; i < n; i++) {
        visited[cur] = i;
        if (possible(cur)) solve(cur + 1);
    }
}

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