[백준] 9663 N-Queen java

문제

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

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

입력

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

출력

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

 

풀이

import java.io.*;

public class Main {
    static int[] dx = {-1, -1};
    static int[] dy = {-1, 1};
    static BufferedReader br;
    static int n, ans;
    static boolean[][] board;

    public static void main(String[] args) throws IOException {
        init();
        for (int i = 0; i < n; i++) {
            dfs(0, i);
        }
        System.out.println(ans);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new boolean[n][n];
    }

    static void dfs(int x, int y) {
        //목적지인가? : n개까지 말을 놓았을 때
        if(x == n-1) {
            ans++;
            return;
        }
		
        //퀸 놓기
        board[x][y] = true;

        //연결된 곳 순회 : x행의 열
        for (int i = 0; i < n; i++) {
            //갈 수 있는가? : 서로 공격할 수 없는 위치
            if(check(x+1, i)) {
                dfs(x+1, i);
            }
        }

        //말 빼기
        board[x][y] = false;
    }

    static boolean check(int x, int y) {
        //세로 줄에 퀸이 있는지 확인
        for (int i = 0; i < n; i++) {
            if(board[i][y]) {
                return false;
            }
        }

        //왼쪽 위, 오른쪽 위 대각선만 알면 된다. (현재 줄에서 놓을 수 있는지만 보면 되기 때문에)
        int xx, yy;
        for (int i = 0; i < 2; i++) {
            xx = dx[i] + x;
            yy = dy[i] + y;
            while(xx >= 0 && yy >= 0 && xx < n && yy < n) {
                if(board[xx][yy]) {
                    return false;
                }
                xx += dx[i];
                yy += dy[i];
            }
        }

        return true;
    }
}

백트래킹의 대표격인 문제이다. dfs로 백트래킹의 개념을 배우기 좋다.

 

n+n의 체스판에 n개의 퀸이 서로 죽일 수 없게 놓으려면 결국 각 줄 마다 한개씩은 놓아져 있어야 한다.

 

이 점을 활용해서 0,0부터 말을 놓고 다음 줄에서 갈 수 있는 위치로 dfs해서 쭉 가다가 더 이상 놓을 곳이 없다면 자연스레 빠져나오게 된다. 만약 n개의 말이 놓아졌다는 것은 모든 n개의 말이 서로 공격할 수 없게 놓았다는 뜻이므로 답 + 1 해주고 다시 빠져나오면 된다.