[9663] N-Queen

 

얼핏 보면 2차원배열로 퀸을 놓으면 안되는 자리만 체크해주면 쉽게 풀릴듯하다. 그렇게 보고 푸는 아이디어만 생각하고 검색을 해봤다.

그런데... 다들 1차원 배열로 풀었다. 2차원으로 풀면 시간초과가 난다고...

그래서 다른 사람들의 풀이를 참고하였다. 

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static int n;
	static int result = 0;
	static int[] map;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		map = new int[n + 1];
		
		for(int i=1; i<=n; i++) {
			map[1] = i;
			dfs(1);
		}
		System.out.println(result);
	}
	
	public static void dfs(int cnt) {
		
		if(cnt == n) {
			result++;
		}
		
		for (int i = 1; i <= n; i++) {
			if (check(i, cnt+1)) {
				map[cnt+1] = i;
				dfs(cnt+1);
			}
		}
		
	}
	
	public static boolean check(int x, int cnt) {
		
		for(int i=1; i<cnt; i++) {
			if(x == map[i] || Math.abs(x - map[i]) == Math.abs(cnt - i)) {
				return false;
			}
		}
		return true;
	}
}

하고나면 코드가 매우 간단한데....

이런 접근법을 어떻게 생각해야하는걸까