[Java] SW Expert Academy 2806번 문제: N-Queen(DFS, BackTracking, 백트래킹)

--- 문제 ---

• 2806번 : N-Queen

 

--- 코드 ---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Sw2806 {
	
	public static int[] arr;
	public static int sum;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("./src/2806.txt"));

		Scanner sc = new Scanner(System.in);
		
		int T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++) {
			
			int n = sc.nextInt();
			sum = 0;
			arr = new int[n];
			
			dfs(0,n);
			System.out.printf("#%d %d%n",test_case,sum);
		}

	}
	
	public static void dfs(int start, int n) {
		if(start==n) {
			sum+=1;
			return;
		}
		
		for(int x=0; x<n; ++x) {
			
			boolean check = true;
			for(int y=0; y<start; ++y) {
				if(arr[y]==x || arr[y]+(start-y)==x || arr[y]-(start-y)==x) {
					check = false;
					break;
				}
			}
			if(check) {
				arr[start]=x;
				dfs(start+1,n);
			}
			
		}
	}

}

 

위 행 부터 차례로 하니까, 위 행에서 밑으로 내려오는 구간만 확인 하면 된다.

int[] arr 에서 index는 행을 뜻 하고, 그 index의 값은 열을 뜻한다.

즉 arr[1] = 2 는 1행의 2열을 뜻 한다.

따라서. backtracking에서 check 구간은

현재의 행보다 이전의 행에서,

• 지금 체스를 넣고자 하는 x 와 같은 열에 놓아져있었으면 안되고 (arr[y]==x)
• 위 행에서 왼쪽 대각선 아래로 내려 오는 구간에 걸쳐 있으면 안되고 (arr[y]+(start-y)==x)
• 위 행에서 오른쪽 대각선 아래로 내려 오는 구간에 걸쳐 있어도 안된다 (arr[y]-(start-y)==x)
  
  

위 세 조건을 만족하는 열에 체스를 넣고,

다음 행으로 넘어가서 또 조건을 만족하는 구간에 체스를 넣고
마지막 행까지 완료를 하게 되면 최종 가능한 조건으로 보고 결과를 1씩 더한다.

 

 

--- 출처 ---

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&

SW Expert Academy