[SWEA] 2806. N-Queen

문제

N X N 크기의 체스판이 주어지고 queen을 체스판에 위치시켜야한다. 이 때 queen은 가로, 세로, 대각선 방향으로 공격할 수 있다.

 

n개의 queen을 체스판에 위치시켜야할 때, 서로 공격할 수 없는 위치에 둘 수 있는 모든 경우의 수를 구하는 문제

 

 

풀이방법

dfs(깊이 우선 탐색)과 backtracking(되추적)을 사용해 풀 수 있는 대표적인 문제로, 완전 탐색으로 모든 경우의 수를 찾되, 유망하지 않은 

 

경우 배제하여 탐색 시간을 높인다.

 

소스코드

package samsung;

import java.util.*;

public class s_2806 {
	static int n, cnt;
	static int[] col;
	
	public static boolean isPromising(int c) {
		for(int i = 1; i < c; i++) {
			if(col[i] == col[c])
				return false;
			if(Math.abs(col[i] - col[c]) == Math.abs(i - c))
				return false;
		}
		return true;
	}
	public static void dfs(int row) {
		if(row == n) {
			cnt++;
		}
		else {
			for(int i = 1; i <= n; i++) {
				col[row + 1] = i;
				if(isPromising(row + 1)) {
					dfs(row + 1);
				}
				else {
					col[row + 1] = 0;
				}
			}
		}
		col[row] = 0;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			n = sc.nextInt();
			col = new int[n+1];
			cnt = 0;
			
			for(int i = 1; i <= n; i++) {
				col[1] = i;
				dfs(1);
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}