[JAVA] 백준 9663번 - N-Queen

 

 

 

📋 코드

import java.util.*;
public class Main {
	
	static int N, ans = 0;
	static boolean check1[] = new boolean[15]; // 상하 방향
	static boolean check2[] = new boolean[30]; // "/"방향의 대각선
	static boolean check3[] = new boolean[30]; // "\"방향의 대각선
	
	private static void DFS(int i) {
		if(i == N + 1) {
			ans++;
			return;
		}
		
		for (int j = 1; j <= N; j++) {
			// (i,j)에 queen을 놓을 수 있을 때
			if(!check1[j] && !check2[i+j] && !check3[i-j+14]) { 
				check1[j] = check2[i+j] = check3[i-j+14] = true;
				DFS(i+1);
				check1[j] = check2[i+j] = check3[i-j+14] = false;
			}
		}
	}
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		DFS(1);
		
		System.out.println(ans);
		
	}
}

 

📕 풀이 방법

💡 NxN의 체스판에 N개의 퀸을 놓기 위해서는
N개의 행에 각각 퀸 1개씩 놓는 방법으로 문제를 접근합니다.

 

static boolean check1[] = new boolean[15]; // 상하 방향
static boolean check2[] = new boolean[30]; // "/"방향의 대각선
static boolean check3[] = new boolean[30]; // "\"방향의 대각선

N의 경우 1~14 사이의 값이 주어지므로 상하 방향에 check를 할 배열(check1[ ])과
대각선 방향에 check 할 배열(check2[ ], check3[ ])을 만들어 줍니다.

 

이해를 돕기 위해 (4,3) 지점에 퀸을 놓는다고 가정했을 때

1. (↕) : 그다음 퀸들은 3열에 놓을 수 없게 되므로 check1[3] = true로 체크해줍니다.

 

2. (↗) : (5,2), (4,3), (3,4), (2,5) 모두 i+j값이 일정합니다. 따라서 check2[i+j] = check2[7] = true로 체크해줍니다.

🙄 혹시... 만약에 퀸이 (3,3)에 놓인다면?

i+j=3+3=6이고, 앞으로 i+j가 6인 대각선 라인에 퀸을 놓을 수 없게 되므로 check2[6] = true로 체크해주면 됩니다!

 

3. (↘) : (2,1), (3,2), (4,3), (5,4) 모두 i-j값이 일정하므로 check3[i-j+14] = check3[15] = true로 체크해줍니다.

🙄 만약에 퀸이 (3,3)에 놓인다면?

i-j+14 = 3-3+14 = 14이고, 앞으로 i-j+14가 14인 대각선 라인에 퀸을 놓을 수 없게 되므로 check3[14] = true로 체크해주면 됩니다!

마찬가지로

(1,14)에 퀸을 놓으면 check3[1-14+14] = check3[1] = true,

(14,1)에 퀸을 놓으면 check3[14-1+14] = check3[27] = true로 체크합니다.

 

 

 

 

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

9663번: N-Queen