📖 [백준알고리즘 풀이] Q.9663 N-Queen 문제 풀이 - java

📖 문제

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

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

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

🔍 접근법

Q.9663 N-Queen 문제입니다.

백트래킹 유형의 대표적인 문제입니다.

N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법을 구하는 문제입니다.

우선 퀸의 배치가 불가능한 경우는 기존의 퀸의 자리의

가로와 세로에 불가능하고 또한 대각선의 위치에도 배치가 불가능합니다.

처음에 체스판 N*N을 2차원 배열로 선언하여

백트래킹을 진행하였지만 퀸을 둘 수 있는지 없는지 확인할 때 이중 for 문을 사용하여 시간초과가 났습니다.

그래서

2차원 배열로 선언한 체스판을

1차원 배열로 선언하여

각 인덱스에는 row로 board[row] 는 column 값으로 넣어주어

백트래킹을 통해 풀이가 가능했습니다.

💻 코드

2차원 배열 풀이 (시간 초과)

public class Main_9663_1 {
    static int N, ans;

    static boolean[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = 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)) {
                board[r][c] = true;
                solve(r + 1);
                board[r][c] = false;
            }
        }
    }

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

        for (int i = 0; i < N; i++) {
            if (board[i][c])
                return false;
            for (int j = 0; j < N; j++) {
                if(Math.abs(r-i) == Math.abs(c-j) && board[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
}

1차원 배열 풀이 (정답)

public class Main_9663_2 {
    static int N, ans;
    static int[] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N];
        ans = 0;
        solve(0);

        System.out.println(ans);
    }

    public static void solve(int row) {
        if(N==row){
            ans++;
            return;
        }
        for(int i=0; i<N; i++){
            board[row] = i;
            if(check(row)){
                solve(row+1);
            }
        }
    }

    public static boolean check(int row) {
        for(int i=0; i<row; i++){
            if(board[i] == board[row] || Math.abs(board[i]- board[row]) == Math.abs(i-row)){
                return false;
            }
        }
        return true;
    }
}

Written on March 12, 2021