[SWEA] N-Queen

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

모든 경우의 수를 구하는 문제로 완전탐색을 통해 해결한다. 이때,

1
2
if (result[d] == result[i] || Math.abs(d-i) == Math.abs(result[d]-result[i])) 
				return false;

를 통해 퀸이 놓쳐질 수 없는 경우를 체크할 수 있다.

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;

public class Solution {

	static int count;
	static int[] result;
	static int N;
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1;tc<=T; tc++) {
			N = sc.nextInt();
			result = new int[N];
			count = 0;
			NQueen(0);
			System.out.println("#"+tc+" "+count);
		}
	}
	
	static void NQueen(int d) {
		if ( d == N ) {
			count++;
			return ;
		}
		
		for(int i=0; i<N; i++) {
			result[d] = i;
			if( isOk(d) ) {
				NQueen(d+1);
			}
		}
	}
	
	static boolean isOk(int d) {
		for(int i=0; i<d; i++) { // 지금 테스트할 퀸 이전 퀸들의 위치들 보면서 괜찮은지 판단하기. 
			if (result[d] == result[i] || Math.abs(d-i) == Math.abs(result[d]-result[i])) {
				return false;
			}
		}
		return true;
	}
	
   
}