[삼성 SW EA] N-Queen 백트레킹

백트레킹이란? 특정 노드의 유망성(Promising)을 검사하고 유망하다면 자식 노드로, 유망하지 않다면 그 다음 부모 노드로 탐색을 하는 것이다.

N-Queen은 N*N개의 체스판에서 N개의 Queen이 서로 열, 행, 대각으로 겹치지 않는 경우의 수를 구하는 것이다.

첫 번째 부모(첫 번째 행)는 1~n까지의 열을 가질 수 있고

두 번째 부모(두 번째 행)은 1~n까지의 열을 가질 수 있고 -> point

세 번째 부모(세 번째 행)은 1~n까지의 열을 가질 수 있고

.

.

.

N 번째 부모(N번째 행)은 1~n까지의 열을 가질 수 있다.

즉 ,배열로 이용하면

a0 a1 a2 .......... an-1 -> 열 

[0] [1] [2] .............[n-1] -> 행

로 표현할 수 있다.(1차원 배열로 나타낼 수 있다!!!!!)

point로 1~N의 행을 만들고 그 안에서 1~N의 열을 반복하여 유망성(Promising)을 검사해본다.

1~point 행까지의 유망성을 검사하면 되므로 배열 값이 같은지(열이 같은지) 비교하고, / 윗방향, \ 윗방향 검사만 해주면 된다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
class Solution {
    static int[][] maps;
    static int answer;
    static int n,queenNum;
    
    public static void main(String[] args) throws FileNotFoundException {
        //Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\SamsungGoGo\\sample_input.txt"));
        int T = sc.nextInt();
        for(int t=1;t<=T;t++){
            answer = 0;
            n=sc.nextInt();
            
            int[] q = new int[n];
             for(int i=0;i<n;i++){
                 q[0]=i;
                dfs(q,0);
            }
            
            System.out.println("#"+t+" "+answer);
        }
    }
 
    private static void dfs(int[] q, int prev) {
        if(prev+1==n){
            answer++;
            return;
        }
        
        for(int i=0;i<n;i++){
            q[prev+1]=i;
            if(isSatisfied(q,prev+1)) dfs(q, prev+1); // 백트레킹
            q[prev+1]=0;
        }
    }
 
    private static boolean isSatisfied(int[] q, int currCount) {
        for(int i=0;i<currCount;i++){
            if(q[currCount] == q[i]) return false; // 같은 열에 있는지 검사 
            if(currCount-i == q[currCount]-q[i]) return false; // / 검사
            if(currCount-i == q[i]-q[currCount]) return false; // \ 검사
        }
        return true;
    }
 
}