121. 9663(N-Queen)

import java.util.*;
import java.io.*;

class Main {
	static int cnt;
	static boolean[] visited;
	static int[] QueenLocation;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		cnt = 0;
		visited = new boolean[N];
		QueenLocation = new int[N];

		DFS(N, 0);
		System.out.println(cnt);
	}

	private static void DFS(int N, int depth) {
		if (depth == N) {
			cnt++;
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				QueenLocation[depth] = i;

				boolean isQLocated = false;
				for (int j = 0; j < depth; j++) {
					if(Math.abs(QueenLocation[depth] - QueenLocation[j]) == Math.abs(depth - j)) {
						isQLocated = true;
						break;
					}
				}
				
				if(!isQLocated) {
					visited[i] = true;
					DFS(N, depth+1);
					visited[i] = false;	
				}
			}
		}

	}
}

문제요약

Queen이 N개 있는데 N*N 체스판에서 Queen이 서로 공격하지 못하게 위치 경우의 수를 구하시오.

설명

N이 4일때를 예를 들어보자.(4*4에서는 2가지가 존재한다.)

다음과 같은 경우에 Queen이 서로 공격할 수 없으므로 문제에 조건이 맞는다.

참고로 (2, 0) 은 (QueenLocation, depth) 혹은 (i, depth) 이다.

 

 

깊이우선 탐색이므로,

	if (depth == N) {
			cnt++;
			return;
		}

끝 깊이까지 도달 했을 때 (n개의 퀸이 서로 공격하지 않는다면) 카운트를 증가시키고 return한다.

 

	if (!visited[i]) {
				QueenLocation[depth] = i;

만약 탐색한 경우가 False라면 QueenNum을 부여한다. 

 

				boolean isQLocated = false;
				for (int j = 0; j < depth; j++) {
					if(Math.abs(QueenLocation[depth] - QueenLocation[j]) == Math.abs(depth - j)) {
						isQLocated = true;
						break;
					}
				}

퀸이 공격을 하는 위치인지 확인을 한다.

 

퀸이 공격을 하지 않는 경우는 다음과 같다.

Math.abs(QueenLocation[depth] - QueenLocation[j]) == Math.abs(depth - j)

대각선을 검토한다.

 

예를 들어 2,2에서 탐색한다고 하자.

행의 차, 열의 차가 (1,1) (1,3) (3,1) (3,3) 으로 나아간다면, 대각선을 컴토하는 것이다.

 

한번 확인을 해보자면 2-1 2-1 같으므로 대각선, 2-1 3-2 같으므로 대각선, 2-3 2-1 (절대값)같으므로 대각선, 2-3 2-3(절대값) 같으므로 대각선.

따라서 대각선으로 뻗어나가는 것을 알 수 있다.

		if(!isQLocated) {
					visited[i] = true;
					DFS(N, depth+1);
					visited[i] = false;	
				}

대각선을 탐색했을 때 퀸이 없다면 DFS 재귀를 실행할 것이다.

 

만약, 행에 Queen이 위치해 있다면, 그 부분은 더 이상 탐색하지 않아도 된다.

따라서 vistied[i]를 true로 둔 것이고,

DFS로 다음 탐색을 진행한다.