[백준/JAVA] 9663번 N-Queen

• 조금 더 복잡한 백트래킹 문제 1
  https://www.acmicpc.net/problem/9663

1. 문제

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

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

2. 문제 접근

1) 첫째 줄에 체스판의 크기 N을 입력받는다.
2) 퀸이 공격할 수 없으려면 한 행에 한개씩 두어야한다.
3) 백트래킹 알고리즘을 사용하여 depth를 행으로 생각, 0부터 N-1까지 반복하며 열을 선택한다.
4) 이때, 열, 2개의 방향의 대각선에 겹치면 안되기 때문에 체크를 하는 boolean형 배열 3개를 선언한다.
5) 열, 2개의 방향의 대각선 모두 겹치지 않을 때 백트래킹 함수를 실행하고 각 체크 배열의 값을 true로 설정한다.
6) 지정한 깊이까지 도달한 경우는 겹치지 않는 경우로 경우의 수를 1 증가시킨다.
7) 모든 경우의 수를 탐색한 후 경우의 수를 출력한다.

3. 코드

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

public class Main {
    static int N;
    static int result = 0;
    static boolean side1[];
    static boolean side2[];
    static boolean column[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        column = new boolean[N];
        side1 = new boolean[2*N-1];
        side2 = new boolean[2*N-1];

        back(0);
        System.out.println(result);
    }

    static void back(int depth){
        if(depth==N){
            result++;
            return;
        }
        for(int i=0;i<N;i++){
            if(!column[i] && !side1[depth-i+N-1] && !side2[depth+i]){
                column[i] = true;
                side1[depth-i+N-1] = true;
                side2[depth+i] = true;
                back(depth+1);
                column[i] = false;
                side1[depth-i+N-1] = false;
                side2[depth+i] = false;
            }
        }
    }
}