[백준 9663] N-Queen 풀이 (JAVA)

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

9663번: N-Queen

이 문제는 backtracking 의 대표적인 문제이다.
익숙하지 않은 기법이기에 문제 풀이하는데에 시간이 많이 소요되었다.

체스판에서 퀸은 가로 세로 대각선으로 무제한 이동 가능하다는 특징이 있다.
따라서 하나의 행에는 단 하나의 퀸만 놓을 수 있다!!
이 점을 토대로 일차원배열을 생성하여 'arr[행] = 열' 로 확인해나가는 것이 핵심이다!!!!

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

public class Main { 
	static int n, count; //경우의 수 카운트 값
	static int[] arr; //체스판

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n]; // 행을 뜻함
		backtracking(0);  //0행 부터 시작!
		System.out.println(count);
	}

	static void backtracking(int row) {
		if (row == n) { //n번째 행은 마지막으로 수행되는 곳이기에 놓을 수 있는 위치는 단 하나이기에 return!
			count++;
			return;
		}
		for (int i = 0; i < n; i++) { //열을 뜻함 
			arr[row] = i; // row행의 i번째 열에 퀀을 놓은다면..? 을 뜻함
			if (isGood(row, i)) { //퀸 자리로써 알맞은지 체크!
				backtracking(row + 1); //다음 행의 퀸 자리 확인하러 가기
			}
		}

	}

	static boolean isGood(int r, int c) {
		for (int k = 0; k < r ; k++) {
			if (c == arr[k] || Math.abs(r - k) == Math.abs(c - arr[k])) {
            	//같은 열이면 탈락, 행-행과 열-열의 차이가 같으면 대각선 위치이기에 탈락
				return false;
			}
		}
		return true;
	}

}