[BOJ-9663] N-Queen - JAVA 풀이

N-Queen

문제

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

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

---

입력

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

출력

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

---

예제 입력

8

예제 출력

92

---

아이디어

• 대표적인 백트래킹 문제다 휘발되기 전에 정리해보자..
• 대각선에 놓을 수 없고 매 행마다 열, 대각선에 놓일수 없는지를 체크해야한다
• 어떤 영상인지는 정확히 기억은 안나지만 백트래킹을 이해하기 좋은 비유가 있었는데 도미노를 하나씩 놓고 마지막에 놓은 도미노를 넘어뜨리는걸 연상하라는 내용이었다 확실히 이미지로 기억하면 도움이 되는거 같다

---

JAVA 풀이

import java.io.*;

public class Main {

    static int N;
    static int cnt;
    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];

        recur(0);
        br.close();
        System.out.println(cnt);
    }

    static void recur(int queen) {

        // 갯수 확인
        if (queen == N) {
            cnt++;
            return;
        }

        for (int i = 0; i < N; i++) {
            board[queen] = i;
            if (check(queen)) {
                recur(queen + 1);
            }
        }

    }

    static boolean check(int col) {

        for (int i = 0; i < col; i++) {
            if (board[col] == board[i]) {
                return false;
            } else if (Math.abs(col - i) == Math.abs(board[col] - board[i])) {
                return false;
            }
        }
        return true;
    }
}