[백준] 9663 - N-Queen (java)

문제

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

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

입력

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

출력

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

예제 입력

8

예제 출력

92

코드

import java.io.*;

public class Main {
    static int N;
    static int cnt = 0;
    static int[] col;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        col = new int[N];

        dfs(0);
        bw.write(cnt + "\n");

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

    static void dfs(int x) {
        if (x == N) { // 마지막 행일 때
            cnt++;
        } else {
            for (int i = 0; i < N; i++) {
                col[x] = i;     // 오른쪽으로 한칸씩 이동
                if (isValid(x)) {   // 퀸을 놓을 수 있으면
                    dfs(x + 1); // 다음 줄로 이동
                }
            }
        }
    }

    static boolean isValid(int level) {
        for (int i = 0; i < level; i++) {   // 위에 놓여진 퀸들과 비교
            if (col[i] == col[level] || Math.abs(col[level] - col[i]) == level - i) {   // 같은 열이거나 대각선으로 겹치는 경우
                return false;
            }
        }
        return true;
    }
}

정리

알고리즘
1. 퀸을 자리에 둔다. (0부터 N-1까지 열을 움직임)
2. 그 자리에 둘 수 있는지 확인한다. (isValid)
- 첫 번째 행부터 놓인 퀸들과 비교하여 같은 열인지, 대각선에 있는지 확인한다.
3. 가능하다면 다음 행으로 이동한다. (재귀 호출)
4. 1~3을 반복하다가 마지막 행인 경우, 카운트해 준다.