백준 9663 JAVA : N-Queen

문제

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

9663번: N-Queen

 

풀이 예상

행: 인덱스, 열: 값 으로 나타내는 1차원 배열로 2차원 체스판을 구현할 것이다.

0번째 행부터 각 칸에 체스를 놓고 놓아도 되는지 확인 후 가능하다면 다음 행을 진행한다.

check함수에서는 현재 행에 놓은 체스말의 위치가 세로로 같은지 확인과 대각선에 체스가 있는지 확인해야한다.

세로로 같은지는  배열값으로 확인할 수 있고 대각선에 있는지는 기울기가 1인 걸로 확인할 수 있다.

 

풀이방법 (접근 방법 & 시간복잡도)

 

시간복잡도 => O(N!)

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

public class Main {
    static int N;
    static int[] board;
    static int answer;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N]; //행 -> 인덱스, 열 -> 값

        queen(0);

        System.out.println(answer);

    }

    private static void queen(int depth) {
        if(depth == N) {
            answer++;
            return;
        }
        for (int i = 0; i < N; i++) {
            board[depth] = i;
            if(check(depth)) {
                queen(depth+1);
            }

        }

    }
    static boolean check(int depth) {
        for (int i = 0; i < depth; i++) { //세로로 같은 칸이 있는지, 대각선에 위치 해 있는지
            if(board[i] == board[depth] || (depth - i == Math.abs(board[depth] - board[i]))) return false;
        }
        return true;
    }

}

결과