[백준] 9663번 N-Queen JAVA 백트래킹

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

9663번: N-Queen

 

문제 요약

N*N 체스판에서 퀸 N개를 배치할 수 있는 방법의 수를 구하는 문제

퀸들은 서로를 공격할 수 없는 위치에 배치되어야 한다.

풀이 방법

모든 경우의 수를 탐색하되 중간에 안 되는 수가 나오면 그 뒤는 체크하지 않는 백트래킹 문제이다.

퀸의 이동 가능 경로는 해당 열 전부와 대각선 전부이다.

고로 1열부터 하나씩 배치해보며 n개가 배치되는 경우의 수를 더해준 후 출력하면 된다.

크게 2가지 구성인데

1번은 퀸이 n개 배치되었는지 확인 후 배치되었으면 결괏값 +1 

아직 진행 중이면 배치 가능 한 위치를 탐색하는 재귀 함수

2번은 재귀 함수에서 배치 가능한 위치를 탐색할 때 사용할 탐색 함수다.

 

2번에서 배치 가능한지에 대한 판단을 예를 들어 설명하면

n=4이고 3번째 퀸을 놓을 차례이면

1번 2번 퀸이 놓아진 열이 아니며 대각선 위치가 아닌 위치를 선정한다.

이때 놓아진 열은 배열에 저장해 index는 순번 값은 위치로 할당해 사용했다.

대각선인지 아닌지에 대한 판단은 

 

Q X X X

X Q X X
X X X X

 

이런 경우 배열은

arr[0] = 0, arr[1] = 1 이 된다.

고로 각 인덱스의 차 != 각 값의 차 이면 대각선에 위치하지 않는다고 판단할 수 있다.

코드

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

public class Main {

    static int size;
    static int cnt = 0;
    static int[] arr;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(br.readLine());
        arr = new int[size];
        scan(0);
        System.out.println(cnt);
    }

    public static void scan(int depth) {
        //전체 퀸이 배치되었다면 경우의 수를 추가한다
        if(size == depth){
            cnt++;
            return;
        }
        //퀸을 배치한다
        for(int i=0; i<size; i++){
            arr[depth] = i;
            if(allocatable(depth)){
                scan(depth+1);
            }
        }
    }
    public static boolean allocatable(int target){
        //target 이전에 놓아진 퀸들의 위치로 공격가능한가 판단한다
        for(int i=0; i<target; i++){
            //같은 행에 위치하는지 체
            if(arr[i] == arr[target]){
                return false;
            }
            //크로스 체크
            if(Math.abs(target-i) == Math.abs(arr[target] - arr[i])){
                return false;
            }
        }
        return true;
    }

}