[SWEA / N-Queen / JAVA]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB 

SW Expert Academy

 

문제 접근

 

이해가 안된다..

다음에 다시 볼 것

import java.util.*;
import java.io.*;

public class Main {
	
	static int[] queen;
	static int count;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			int N = Integer.parseInt(br.readLine());
		    queen = new int[N]; // 퀸이 놓이면 그 행은 아예 놓일 수 없다
		                       // queen[0] = 3   (0,3)에 퀸이 놓였단 뜻
		    count = 0;
		    
		    dfs(0, N);
		    System.out.println("#"+t+" " + count);   
		}
	}
	
	public static void dfs(int num, int N) {
		if(num == N) { // 퀸을 맵에 다 놓았을 경우
			count += 1; // 경우의 수 + 1
			return; // 이전 탐색으로 돌아가기
		}
		
		for(int i=0; i<N; i++) { 
			
			boolean check = true; // 퀸을 놓을 수 있는지 여부
			for(int j=0; j<num; j++) {
				//퀸 1개가 놓이면 다음 행에서 어디에 놓일지 찾으면 되기에 j<num까지만
				if(queen[j] == i || queen[j]+(num-j) == i || queen[j]-(num-j) == i) {
					check = false; // 이전 퀸의 열, 좌우 대각선에 겹치면 안된다.
					break;
				}
			}
			// 행을 다 탐색했는데도 이전 퀸과 겹치는 구간이 없으면
			// check는 계속 true이기에 해당 자리에 퀸 놓고 다시 다음 행 탐색
			if(check) {
				queen[num] = i;
				dfs(num+1, N); // 계속 돌면서 퀸을 다 놓고 다시 돌아와서 새로운 구간에 퀸을 놓고 만드는 경우의 수 탐
			}
		}
	}
}