[백준] 9663. N-Queens

문제

 

풀이

처음에는 완전탐색으로 접근했었지만 시간초과로 실패하였다. 그래서 경우의 수를 줄이기 위한 방법을 고민했고 모든 행/열이 아닌 어차피 한 행에는 하나의 Queen만 올 수 있다는 점을 이용해 재귀함수의 깊이를 줄일 수 있었다. 

import java.util.Scanner;

public class NQueens {
	static Scanner sc = new Scanner(System.in);  
	static int result = 0;
	static int N = 0;
	static boolean[][] check;
	static int[] dx = {0, 0, -1, 1, 1 ,1 , -1, -1};
	static int[] dy = {-1, 1, 0 ,0, -1, 1 , 1, -1};
	public static void main(String[] args) {
		N = sc.nextInt();
		for (int i = 0; i < N; i++) {
			check = new boolean[N][N];
			check[0][i] = true;
			nqueen(0,i,1);
		}
		System.out.println(result);
	}
	
	private static void nqueen(int x, int y, int cnt) {
		if (cnt == N ) {
			result += 1;
			return;
		}
		
		for (int j = 0; j < check[0].length; j++) {
			if (j == y || !isValid(x+1, j)) continue;
			check[x+1][j] = true;
			nqueen(x+1, j, cnt + 1);
			check[x+1][j] = false;
		}
	}
	
	static boolean isValid(int x, int y) {	
		for (int i = 0; i < 8; i++) {
			int currentX = x;
			int currentY = y;
			while(true) {
				currentX += dx[i];
				currentY += dy[i];
				if (currentX < 0 || currentX >= N || currentY < 0 || currentY >= N) break;
				if (check[currentX][currentY]) {
					return false;
				}
			}
		}
		return true;
	}
}

 

정답은 맞긴한데 수행 시간이 너무 오래 걸려서 다른 사람들의 코드를 참고해봤다. 먼저 2차원 배열을 이용하지 않고 1차원 배열을 사용해서 인덱스가 행으로 값이 놓은 열의 위치를 나타내도록 구현했다는 점, 그리고 나는 놓을 수 있는 위치를 찾기 위해 delta 배열을 만들어서 모든 방향에 대해 탐색을 했는데, 이를 이용해서 놓을 수 있는지 판단하는 부분을 최적화 한 부분이 나와 다른 부분이었다.

최적화 해답

import java.util.Scanner;

public class NQueens {
	static Scanner sc = new Scanner(System.in);  
	static int result = 0;
	static int N = 0;
	static int[] row;
	public static void main(String[] args) {
		N = sc.nextInt();
		row = new int[N];
		int depth = 0;
		nqueen(depth);
		System.out.println(result);
	}
	
	private static void nqueen(int depth) {
		if (depth == N) {
			result += 1;
			return;
		}
		
		for (int i = 0; i < N; i++) {
			row[depth] = i;
			if (isValid(depth)) {
				nqueen(depth + 1);	
			}
		}
	}
	
	static boolean isValid(int depth) {	
		for (int i = 0; i < depth; i++) {
			if (row[i] == row[depth]) 
				return false;
			if (Math.abs(row[i] - row[depth]) == Math.abs(i - depth)) 
				return false;
		}
		return true;
	}
}