백준 9663 N-QUEEN

N-QUEEN : https://www.acmicpc.net/problem/9663

9663번: N-Queen

dfs의 기본 N-Queen을 풀었다.

NXN 배열에 N개의 퀸을 서로 죽일수 없는 위치에 놓는 가짓수를 구하는 문제였다.

N이 최대 15까지라 안터질줄알고 stack을 사용하여

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static int N = 0, answer = 0;
	public static int[][] map = null;
	public static Stack<int[]> stack = null;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		stack = new Stack<int[]>();
		dfs(0, 0, 0);
		System.out.println(answer);
	}

	private static void dfs(int count, int starty, int startx) {
		if (count == N) {
				answer++;
			return;
		}

		for (int y = starty; y < N; y++) {
			for (int x = y == starty ? startx : 0; x < N; x++) {
				stack.push(new int[] { y, x });
				if (checkCommon()) {
					dfs(count + 1, y, x + 1);
				}
				stack.pop();
			}
		}
	}

	private static boolean checkCommon() {

		for (int i = 0; i < stack.size(); i++) {
			int[] pos1 = stack.get(i);
			for (int j = i + 1; j < stack.size(); j++) {
				int[] pos2 = stack.get(j);

				if (IsZero(pos1, pos2)) {
					return false;
				}
			}
		}
		return true;
	}

	private static boolean IsZero(int[] pos1, int[] pos2) {
		// pos1과 pos2의 위치가 상우하좌 위치에 있을경우
		if (Math.abs(pos1[0] - pos2[0]) == 0 || Math.abs(pos1[1] - pos2[1]) == 0) {
			return true;
		} else if (Math.abs(pos1[0] - pos2[0]) == Math.abs(pos1[1] - pos2[1])) {
			return true;
		}
		return false;
	}
}

이런식으로 구현 하였다.

하지만 가지치기를 안하고 Stack을 list로 바꾸는데 시간이 많이 들어서일까 속도도 너무느리고 설상가상으로 메모리까지 초과가 났다.

따라서

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static int N = 0, answer = 0;
	public static int[][] map = null;
	public static int[] arr = null;
	public static boolean[] visitx = null, visity = null;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		arr = new int[N];
		visitx = new boolean[N];
		visity = new boolean[N];
		dfs(0);
		System.out.println(answer);
	}

	private static void dfs(int count) {
		if (count == N) {
			answer++;
			return;
		}

		for (int x = 0; x < N; x++) {
			boolean option = true;
			for (int y = 0; y < count; y++) {
				if (arr[y] == x || Math.abs(x - arr[y]) == Math.abs(count - y)) {
					option = false;
					break;
				}
			}
			if (option) {
				arr[count] = x;
				dfs(count + 1);
			}
		}
	}
}

이런식으로 가지치기를 하였다

평소 좌표를 new int[]{y,x}형태로 가지고 다녔는데 int형 배열 하나로 모든 좌표를 처리할 수 있었던 문제 였다.

또한 오랜만에 가지치기 문제를 풀어보는 좋은 경험이었다.