[백준 알고리즘 - 9663] N-Queen - java(재귀호출, 백트래킹)

사실 백트래킹을 처음 접해봤는데 n-Queen 문제가 대표적인 백트래킹 문제라고 한다.

일반적인 DFS와 같은 완전탐색은 문제해결 과정에서 현재 탐색하는 경우가 조건에 부합한지 부합하지 않은지를 그 경우를 실행하고 나서야 알 수 있다. 실행하고 나서 if 조건으로 다시 이전 상태로 돌아간다고 하더라도 그 효율성은 떨어질 수밖에 없다.

백트래킹은 이 단점을 살짝 보완한 것인데,

해당 경우를 실행하기 전에 조건에 부합한지의 여부를 먼저 판별하고 부합하지 않으면 원래 상태로 돌아가고,

부합한다면 해당 경우를 수행한 뒤 다시 원래 상태로 돌려놓는 것을 말한다.

import java.util.Scanner;
import java.util.Set;



class Main{
		public static int queen(int row, int n,int count, boolean[] eqrow, boolean[] rightdae, boolean[] leftdae) {
			if(row>=n && count<n)//맨 마지막 row까지 왔는데 퀸을 모두 배치하지 않았다.
				return 0;
			
			if(row>=n && count==n) //성공조건 
				return 1;
			
			
			int result=0;
			
			for(int i=0; i<n; i++) {//(row, i) 
				if(eqrow[i]==true)//같은 줄에 퀸이 있는지?(유망한지?)
					continue;
				if(rightdae[row+i]==true)//오른쪽 대각선에 퀸이 있는지?(유망한지?)
					continue;
				if(leftdae[i-row+n-1]==true)//왼쪽 대각선에 퀸이 있는지?(유망한지?)
					continue;
               //continue를 통해 원래 상태로 돌아감

                //탐색할 수 있는 위치라면?
				eqrow[i]=true;
				rightdae[row+i]=true;
				leftdae[i-row+n-1]=true;
				
				result+=queen(row+1, n, count+1, eqrow, rightdae, leftdae ); // 탐색한다 

                 //원래상태로 복귀
				eqrow[i]=false;
				rightdae[row+i]=false;
				leftdae[i-row+n-1]=false;
					
				
			}
			
			return result;
		}
	
       public static void main(String[] args){
    	   Scanner scan=new Scanner(System.in);
    	   int n=scan.nextInt();
    	   boolean[] eqrow=new boolean[n];
    	   boolean[] rightdae=new boolean[n*n];
    	   boolean[] leftdae=new boolean[n*n];
    	   System.out.println(queen(0, n, 0 , eqrow, rightdae, leftdae));
    	   
       }
       
       
}