[BOJ] 9663. N-Queen (Java)

[BOJ] 9663. N-Queen (Java)

Problem

제출일 : 2020-03-13

문제 풀이 시간 : 2H

난이도 : ★★★★

---

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

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

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

Input

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

Output

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

Example

input

8

output

92-2 5 -3 1

Solution & Inpression

기본 적인 백트래킹 문제.

아래 애니메이션을 보면 해를 탐색하는 과정을 알 수 있다.

기본적으로 백트래킹은 map을 돌며 해당 위치에 가로, 세로, 대각선으로 중복되지 않게 말을 놓을 수 있는지 확인하고 된다면 다음 말을 놓고 아니면 이전 말의 위치를 변경하는 방법으로 문제를 해결하면 된다.

처음 시도한 코드는 시간초과가 발생했다. 당연히 시간 초과가 발생할것이다. 시간 복잡도를 따져보면 말을 놓을 수 있는 경우의 수는 $_{N\times N}P_N$가 될 것이고 가지치기는 $O(N^2)$의 시간이 소요될것이다.

검사를 해야 하는 항목이 열을 사용하는지 같은 대각선 내에 있는지를 확인하면 되기에 boolean배열을 이용하여 문제를 해결하였다.

Code 1

언어 : JAVA

결과 : 시간 초과

import java.util.Scanner;

public class Main {
    static int N, ans;

    static boolean[][] map;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        map = new boolean[N][N];

        ans = 0;
        solve(0);
        System.out.println(ans);
    }

    public static void solve(int r) {
        if (r == N) {
            ans++;
            return;
        }
        for (int c = 0; c < N; c++) {
            if (check(r, c)) {
                map[r][c] = true;
                solve(r + 1);
                map[r][c] = false;
            }
        }
    }

    public static boolean check(int r, int c) {
        if (map[r][c])
            return false;

        for (int i = 0; i < N; i++) {
            if (map[i][c]) // 행 검사
                return false;
            for (int j = 0; j < N; j++) {
                if (i + j == r + c && map[i][j]) // 대각선 검사(/방향)
                    return false;
                if (i - j == r - c && map[i][j]) // 대각선 검사(\방향)
                    return false;
            }
        }
        return true;
    }
}

Code 2

언어 : JAVA

메모리 : 14912 kb

실행 시간 : 2764 ms

import java.util.Scanner;

public class Main {
    static int N, ans;

    static boolean[] col, slash, backslash;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        col = new boolean[N];
        slash = new boolean[2 * N - 1];
        backslash = new boolean[2 * N - 1];

        ans = 0;
        solve(0);
        System.out.println(ans);
    }

    public static void solve(int r) {
        if (r == N) {
            ans++;
            return;
        }
        for (int c = 0; c < N; c++) {
            if (check(r, c)) {
                col[c] = slash[r + c] = backslash[r - c + N - 1] = true;
                solve(r + 1);
                col[c] = slash[r + c] = backslash[r - c + N - 1] = false;
            }
        }
    }
    public static boolean check(int r, int c) {
        if (col[c] || slash[r + c] || backslash[r - c + N - 1])
            return false;
        return true;
    }
}