[백준]#9663 N-Queen

문제

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

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

입력

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

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

풀이

이 문제는 DFS 알고리즘을 이용해서 풀었다.

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

public class Main {
    static int N;
    static int[][] map;
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        cnt = 0;
        for(int i=0; i<N; i++) {
            map[i][0] = 1;
            dfs(0, 1);
            map[i][0] = 0;
        }

        System.out.println(cnt);
    }

    public static void dfs(int y, int idx) {
        if(idx==N) {
            cnt++;
            return;
        }

        for(int i=0; i<N; i++) {
            if(check(i, y+1)) {
                map[i][y+1] = 1;
                dfs(y+1, idx+1);
                map[i][y+1] = 0;
            }
        }
    }

    public static boolean check(int x, int y) {

        for (int i = y-1; i>=0; i--) {
            if(map[x][i]==1) return false;
        }

        int nx = x-1;
        int ny = y-1;

        while(true) {
            if(nx<0 || ny<0) break;
            if(map[nx][ny]==1) return false;
            nx--;
            ny--;
        }

        nx = x+1;
        ny = y-1;

        while(true) {
            if(nx>=N || ny<0) break;
            if(map[nx][ny]==1) return false;
            nx++;
            ny--;
        }
        return true;
    }
}