[백준] 9663 N-Queen - Backtracking / Java

• 문제 링크

9663번: N-Queen

 

• 풀이 과정

탐색을 할 체스판을 1차원 배열로 정의하고 퀸의 위치의 열을 배열의 인덱스 값,

행을 배열의 원소의 값으로 간주하여 접근한다.

 

예를 들어 n = 4 이고 배열의 값이 [2, 0, 1, 3] 일 경우 체스판의 퀸의 위치는 아래와 같다.

기본적으로 퀸은 자신의 위치 기준 가로, 세로, 대각선을 모두 차지한다.

각각의 퀸을 놓을 수 있는 자리를 탐색할 때 depth 는 행을 의미하며

재귀적으로 0 ~ n 까지의 해당 열의 모든 행을 검사한다.

각 행이 다른 퀸과 동일한 행에 위치하거나 대각선에 위치하여 검사하는 함수를 생성하여

해당 위치가 간섭받을 경우 false 를 반환하고 이는 아직 해당 열에 퀸이 없으므로 다음 행을 재귀 호출하여 탐색,

간섭받지 않아 true 를 반환한다면 이미 해당 열에 퀸이 존재하므로 다음 열로 이동한다.

 

col == i 는 해당의 열의 행이 다른 퀸이 위치한 행에 의해 간섭받는 경우이고

대각선을 검사하는 방식을 나타내면 아래와 같다.

Q		2
2		?

col, i 은 열을 의미하고 arr[col], arr[i] 는 행을 의미한다.

? 가 검사하고자 하는 위치일 경우 열의 차와 행의 차가 일치할 경우, 다른 퀸의 대각선에 간섭받는 경우이며

음수가 나오는 경우를 위해 절대값으로 계산한다.

 

이렇게 각 열의 행을 모두 검사하여 퀸을 배치하였을 시 cnt++를 수행하고,

재귀적으로 호출하여 퀸을 배치할 수 있는 모든 경우의 수가 최종적으로 출력된다.

 

• 풀이 코드

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

public class Main {

	static int n;
	static int[] arr;
	static int cnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
		arr = new int[n];

		recur(0);

		bw.write(cnt + "\n");
		bw.flush();
	}

	private static void recur(int depth) {
		if (depth == n) {
			cnt++;
			return;
		}

		for (int i = 0; i < n; i++) {
			arr[depth] = i;

			if (check(depth))
				recur(depth + 1);
		}
	}

	private static boolean check(int col) {
		for (int i = 0; i < col; i++) {
			if (arr[col] == arr[i])
				return false;
			else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i]))
				return false;
		}

		return true;
	}
	
}