[백준] 9663 : N-Queen

문제 출처: https://www.acmicpc.net/problem/9663

소요 시간 : 시도 (1h 20m) + 풀이 (20m)

---

문제

---

시도

 

2차원 boolean 배열을 이용한 백트래킹을 시도했다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    private static int n;
    private static int cases = 0;
    private static boolean[][] board;

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

        // 입력 : N (1 ~ 15) -> N x N의 판에 N개의 퀸
        n = Integer.parseInt(br.readLine());
        board = new boolean[n][n];

        nQueen(0, 0);

        System.out.print(cases);
    }

    private static void nQueen(int i, int j) {
        // 너비가 최댓값을 넘었을 때, 성공 경우를 출력하고 종료
        if (j == n) {
            boolean flag = false;
            for (int y = 0; y < n; y++) {
                if (board[i][y]) {
                    flag = true;
                    break;
                }
            }

            if(flag)
                nQueen(i + 1, 0);
            else
                return;
        }

        // 높이가 최댓값을 넘어섰을 때, 성공 경우를 1 늘리고 return
        if (i == n) {
            cases++;
            return;
        }

        // 만약 확인 후 적합한 자리라면 다음 높이로 넘어가기
        if (check(i, j)) {
            board[i][j] = true;
            nQueen(i + 1, 0);
        }

        // 다음 높이를 갔다 왔거나 적합하지 않은 자리라면 다음 너비로 넘어가기
        board[i][j] = false;
        nQueen(i, j + 1);
    }

    private static boolean check(int x, int y) {
        // Upper Left Diagonal Check
        for (int i = x, j = y; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j]) return false;
        }

        // Same Column Check
        for (int i = x; i >= 0; i--) {
            if (board[i][y]) return false;
        }

        // Upper Right Diagonal Check
        for (int i = x, j = y; i >= 0 && j < n; i--, j++) {
            if (board[i][j]) return false;
        }

        return true;
    }
}

 

시도는 성공했지만, 정석적인 풀이와 비교했을 때 메모리를 조금 더 많이 사용하고, 시간의 경우 2배 이상 차이가 난다는 걸 보고 다른 사람의 풀이도 참고하기로 했다.

---

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static int n;
    private static int count = 0;
    private static int[] board;

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

        // 입력 : N (1 ~ 15) -> N x N의 판에 N개의 퀸
        n = Integer.parseInt(br.readLine());
        board = new int[n];

        nQueen(0);

        System.out.print(count);
    }

    private static void nQueen(int depth) {
        if (depth == n) {
            count++;
            return;
        }

        for (int i = 0; i < n; i++) {
            board[depth] = i;

            if (possibility(depth)) {
                nQueen(depth + 1);
            }
        }
    }

    private static boolean possibility(int col) {
        for (int i = 0; i < col; i++) {
            // 해당 열의 행과 i열의 행이 일치할 경우 (같은 행에 존재할 경우)
            // 혹은 대각선상에 놓여있는 경우
            if(board[col] == board[i] || Math.abs(col - i) == Math.abs(board[col] - board[i]))
                return false;
        }

        return true;
    }
}

 

boolean 2차원 배열이 아닌 int 1차원 배열로 메모리 사용을 줄이고, 퀸 자리 확인 로직도 간략한 매우 깔끔한 풀이가 인상 깊었다.

 

참고 출처: https://st-lab.tistory.com/118

---

알게 된 점

 - 대각선의 성질 : '열의 차와 행의 차가 같으면 서로 대각선에 위치한 것'