[9663번] Queen (완탐, 1차원 배열로)

퀸은 상 하 좌 우 대각선으로 움직일 수 있다.
즉, 같은 행 같은 열 대각선에 놓을 수 없다는 것이다.
1차원 배열은 board를 선언했고
인덱스 번호는 각 행의 번호를 의미하고, 배열의 값은 각 행의 열의 번호를 의미한다.

시작 )
0,0 부터 시작한다.
board[0] = 0 이다.
0행은 둘 수 없으므로 1행부터 탐색한다.

같은 열인지 판단하거나 대각선인지 판단한다.
board[0] (0행 0열에 queen이 놓인 상태, 즉 0이다) 과 현재 행의 열인 0을 비교한다.
0 == 0 으로 같은 열에 놓여져 있으므로 Queen은 놓여질 수 없고 1,1을 판단한다.

(1,1)은
board[0] (값은 0) != 1 이므로 다른 열에 놓여져있다.

그렇다면 대각선인지 판단해보자.
board[0] (의미는 0열) - col(현재 1열) == 0(0행) - 1(현재 1행)
이전 위치에서 가로와 세로가 1만큼 차이나는 것이므로 대각선에 놓여진 것을 알 수 있다.
따라서, Queen은 놓여질 수 없고 1,2를 판단한다.

위의 과정을 반복하면 아래와 같은 일반식이 나올 수 있다.

board[prow] == col || Math.abs(board[prow] - col) == Math.abs(prow - row) 

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

public class Main {
	static int N;
	static int[] board;
	static int cnt = 0;

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

		getQueensCount(0);
		System.out.println(cnt);
	}

	static void getQueensCount(int row) {
		//퀸은 같은 행, 같은 열, 대각선으로 움직일 수 있다.

		if (row == N) { //행을 끝까지 다 돌면
			cnt++;
			return;
		}

		for (int col = 0; col < N; col++) { //현재 행의 열을 탐색
			boolean isP = true;

			//놓을 수 없는 경우
			//prow: 이전까지의 행
			for (int prow = 0; prow < row; prow++) { //현재 탐색 위치와 이전 행을 비교

				//이전의 행의 열과 현재 행의 열이 같거나 || 이전의 행에 놓여진 퀸의 대각선 방향과 같다면
				//대각선 탐색 : 이전 행의 열에서 현재 행의 열의 좌표를 뺀 것의 절대값 == 이전 행의 값과 현재 행의 좌표를 뺀 것의 절대값
				if (board[prow] == col || Math.abs(board[prow] - col) == Math.abs(prow - row)) {
					isP = false;  //놓을 수 없음
					break;
				}
			}

			//놓을 수 있는 경우
			if (isP) {
				board[row] = col;
				getQueensCount(row + 1);
			}
		}
	}
}

https://www.acmicpc.net/problem/9663