BOJ - N-Queen

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

---

Problem

---

Solve

Queen이 서로 공격할 수 없는 모든 경우의 수를 찾아야하는 문제입니다.

위와 같이 N=4인 2차원배열에서 Queen이 놓여져있다면 각 퀸들이 서로를 공격할 수 없는 경우입니다.

이를 1차원 배열로 간단하게 표시가 가능합니다.

1차원 배열을 int[] arr로 정의하였을떄, arr의 index는 Queen이 놓이는 세로, arr[index]의 값은 Queen이 놓이는 가로로 정의할 수 있게 됩니다.

그리고 1차원 배열로 표현함으로써 index가 세로이므로 index를 이동하면서 각 배열의 값이 수직, 수평, 대각선이지 않는 조건을 만족한다면 서로 공격할 수 없는 Queen을 놓는 자리라고 나타낼수 있게됩니다.

그러므로 해당 index에서 지정할 가로값(value)가 이전의 index이 지정한 세로값과 가로값이 수직, 수평, 대각선이 되는지 확인하고 만족하지 않는다면 arr[index]에 해당 value를 지정하고 다음 index와 비교하면 됩니다.

index로 다음 세로값을 비교하기 때문에 수평으로 만나지 않음은 항상 만족합니다.

int[] check라는 1차원 배열을 통해 현재 index에서 value로 정의할 가로값이 이전 index에서 선언한 value인지를 확인할 수 있습니다.

현재 index와 value가 이전 index와 value와 대각선여부인지 확인은 두 좌표의 값이 (y2-y1)/(x2-x1) == 1을 만족한다면 기울기 1을 만족하는 두 좌표이기 때문에 대각선이여서 서로를 공격할 수 있게됩니다.
즉, y2-y1 != x2-x1인 두 좌표여야 서로 공격하지 못하는 좌표입니다.

if(!check[y2] && Math.abs(y2-y1) != Math.abs(x2-check[y1]))

위의 조건이 true라면 두 좌표가 대각선에서 만나지 않는 좌표입니다.

그리고 index가 N이 되게 된다면 모든 arr에 각 Queen이 서로를 공격하지 못하는 값으로 갱신되어있으므로 answer를 1개 증가시켜줍니다.

---

Code

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 answer;
	static int N;
	static boolean[] check;

	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());

		int[] arr = new int[N];
		check = new boolean[N];

		setQueen(arr, 0);

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static void setQueen(int[] arr, int index) {
    	//y값(index)가 N이 된다면 모든 조건을 만족하도록 Queen을 놓은것이기 때문에 answer를 하나 증가시켜줍니다.
		if (index == N) {
			answer++;
			return;
		}

		//해당 y좌표에서 Queen을 놓을 수 있는 x를 찾아줍니다.
		for (int value = 0; value < N; value++) {
			arr[index] = value;
			if(!check[value] && isCross(arr, index, value)){
				check[value] = true;
				setQueen(arr, index+1);
				check[value] = false;
			}
		}
	}

	//해당 y값과 x값이 이전 y값에서 놓인 Queen과 대각선으로 만나는지 확인합니다.
	static boolean isCross(int[] arr, int currentY, int currentX){
		for(int y=0;y<currentY;y++){
			if(Math.abs(currentY-y)==Math.abs(currentX-arr[y])) return false;
		}

		return true;
	}
}

---

Result

---

Reference