[백준] 9663번 : N-Queen

문제

 

접근 방식

N * N 크기의 체스판에 N개의 퀸들이 서로 공격하지 않게 놓으려면

우선 퀸의 공격 범위를 알아야 한다.

 

퀸은 가로와 세로의 직선과 대각선 모두 자신이 이동하고 싶은 만큼 이동할 수 있는데

이 말은 퀸과 같은 행이나 열 혹은 같은 좌표의 기울기를 가진 대각선을 제외한 곳에만

퀸을 둘 수 있다는 것이다.

 

N과 M시리즈를 풀면서 많이 사용했던 사용 여부를 기록하던

배열 방법을 사용해서 풀면 생각보다 쉽게 풀 수 있다.

 

 

우선 위와 같이 퀸이 하나 존재 한다면 같은 행과 열에는 다른 퀸을 둘 수가 없으니

한 줄에는 하나의 퀸만 둘 수 있고 모든 줄에 퀸이 존재한다면

모든 퀸들이 서로 공격 하지 못하는 위치에 존재하게 되니

이를 재귀 함수의 기저 조건으로 지정해 주면 된다. (X == N)

 

 

다음 줄(초록선)에 퀸을 놓기 위해서는 기존에 놓인 퀸들의

가로, 세로, 대각이 겹치는지 여부를 확인해야 하는데

가로는 이미 다른 줄로 넘어왔기에 여부를 체크할 필요가 없고

세로와 좌우 대각선만 체크 해주면 된다.

 

이를 위해서는 퀸을 놓을 때마다 현재 퀸의 좌표를 기준으로

Y축, 우측상단과 좌측하단을 잇는 대각선, 좌측상단과 우측하단을 잇는 대각선의

방문 여부를 기록해주면 된다.

 

만약 (1, 2), (3, 0) 두 좌표가 존재할 때,

두 좌표의 x + y 값이 서로 동일하기 때문에

이 두 좌표는 우측 상단과 좌측 하단을 잇는 같은 대각선상에 위치하고

(1, 1) (3, 3) 두 좌표가 존재할 때,

두 좌표의 x - y 값이 서로 동일하기 때문에

이 두 좌표는 좌측 상단과 우측 하단을 잇는 같은 대각선상에 위치한다.

 

풀이

public class Main {

	private static int count = 0;
	private static int n;
	private static boolean[] isUsedY;
	private static boolean[] isUsedLeftCross;
	private static boolean[] isUsedRightCross;

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

		n = Integer.parseInt(br.readLine());

		isUsedY = new boolean[n];
		isUsedLeftCross = new boolean[n * 2 - 1];
		isUsedRightCross = new boolean[n * 2 - 1];

		nQueen(0);

		System.out.println(count);
	}

	private static void nQueen(int x) {
		if (x == n) {
			count++;
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!isUsedY[i] && !isUsedLeftCross[x + i] && !isUsedRightCross[x - i + n - 1]) {
				isUsedY[i] = true;
				isUsedLeftCross[x + i] = true;
				isUsedRightCross[x - i + n - 1] = true;
				nQueen(x + 1);
				isUsedY[i] = false;
				isUsedLeftCross[x + i] = false;
				isUsedRightCross[x - i + n - 1] = false;

			}
		}
	}
}