[백준 9663번] N-Quenn - JAVA

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

9663번: N-Queen

풀이

사용한 알고리즘 : 백트래킹

 

풀이전략

아래 그림은 N=4인 경우, 모든 경우의 수를 탐색할 수 있도록 만들어진 상태공간트리이다.

(상태 공간 : 문제의 해답을 탐색하기 위한 탐색 공간,

 상태공간트리 : 탐색 공간을 트리 형태의 구조로 암묵적으로 해석한 트리)

(1,1)은 1번 행 1번째 열에 퀸을 둔다는 의미이다.

 

1. 위와 같은 트리를 탐색하는 중 해당 노드가 이전 노드와 비교했을 경우,

    같은 열 또는 대각선 상에 있는지 확인한다.(promising 놓을 수 있는 자리인지 유망성 체크)

   - 대각선상 겹치는지 확인하는 방법은 Math.abs(col[i]-col[k]) == i-k 인 경우 겹치는 것

2. promising한 경우 하위노드까지 탐색을 진행하고, promising하지 않은 경우엔

  하위 노드 탐색을 하지 않는다.

3. 만약 마지막 행까지 탐색이 진행되었으며, 해당 노드까지 promising하다면 count를 1 증가시킨다.

4. count 값을 출력한다.

 

제출코드

import java.util.Scanner;

public class Main {
    static int resultCount=0;

    static boolean promising(int i,int[] col){
        boolean result=true;
        for(int k=1;k<i;k++){
            if(col[i]==col[k] || Math.abs(col[i]-col[k]) == i-k){
                result=false;
            }
        }
        return result;
    }

    static void n_queens(int i, int[] col){
        int n = col.length-1;
        if(promising(i,col)){
            if(i==n) resultCount++;
            else{
                for(int j=1;j<n+1;++j){
                    col[i+1]=j;
                    n_queens(i+1,col);
                }
            }
        }
    }
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N=scanner.nextInt();

        int col[] = new int[N+1];
        n_queens(0,col);
        System.out.println(resultCount);
    }
}