[백준] 9663번 - N Queen (Gold 4)

문제 링크

백준 9663번 - N Queen (Gold 4)

문제 설명

N x N 크기의 체스판에 N개의 퀸을 서로 공격받지 않도록 하는 자리에 두는 경우의 수를 구한다.
퀸의 공격 범위는 상하좌우와 대각선이다.

정답 코드 및 설명

퀸을 하나씩 놓아보다가 안되면 돌아오는 방식의 백트래킹이다.
알고리즘의 구현 자체는 어렵지 않았으나, 시간 초과와 메모리 초과를 해결하는 과정이 문제였다.
결정적인 해결책이 된 것은 “한 행에는 퀸이 한 개만 들어올 수 있다”는 사실이었다.
퀸이 한 행 당 한 개씩만 들어올 수 있으므로, m번째 퀸이 들어갈 위치를 고려할 때 m행의 몇번째 열에 들어갈 지만 생각하면 된다.

import java.io.*;

public class Main {

    static int N, ans = 0;
    static int chess[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        chess = new int[N];
        NQueen(0);
        bw.write(ans + "");
        bw.close();
    }

    static void NQueen(int num) {
        if (num == N) {
            ans++;
            return;
        }
        for (int x = 0; x < N; x++) {
            if (num == 0 || isAble(chess, num, x)) {
                chess[num] = x;
                NQueen(num + 1);
            }
        }
    }

    static boolean isAble(int chess[], int num, int x) {
        boolean isAble = true;
        for (int i = 0; i < num; i++) {
            isAble = isAble && !attack(chess[i], i, x, num);
        }
        return isAble;
    }

    static boolean attack(int cx, int cy, int dx, int dy) {
        return cx == dx || cy == dy || cx + cy == dx + dy || cx - cy == dx - dy;
    }
}