[백준] 9663.N-Queen - Java

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

 

 

⭐️ 중요 포인트

1. |y1 - y2| / |x1 - x2| = ±1 이면 동일한 대각선 위에 위치한다라는 점을 이용

(단, 여기서 나눗셈 연산을 하게 되면 부동소수점 또는 zero division 에러가 날 수 있기 때문에 이항해서

|y1 - y2| = |x1 - x2| 조건이 만족하면 동일한 대각선 위에 존재한다고 구현)

import java.util.*;
import java.io.*;

public class P9663 {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    static int N;
    static int answer;
    static int[] board; // board의 index가 y, value가 x

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        board = new int[N];
        answer = 0;
    }

    static boolean isPossible(int x, int y) {
        for (int i = 0; i < y; i++) {
            if (board[i] == x || Math.abs((y - i)) == Math.abs(x - board[i])) {
                return false;
            }
        }
        return true;
    }

    static void recursion(int y) {

        if (y == N) {
            answer++;
            return;
        }


        for (int x = 0; x < N; x++) {
            if (isPossible(x, y)) {
                board[y] = x;
                recursion(y + 1);
            }
        }



    }


    public static void main(String[] args) throws IOException {
        init();

        recursion(0);

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();

    }
}