백준 9663번: N-Queen [JAVA]

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

9663번: N-Queen

* 풀이

첫번째 시도에서는 N x N 크기의 2차원 배열을 만들어 가능한 퀸의 자리를 모두 체크하는 방식을 떠올렸지만 잘 되지 않았다.

하지만 퀸끼리는 1) 같은 행 2) 같은 열 3) 대각선에 놓을 수 없기 때문에 1차원 배열로도 표현할 수 있었다.

x축을 인덱스, y축을 값으로 보아 [1,3,0,2] 라면 0열 1행, 1열 3행, 2열 0행, 3열 2행에 퀸이 놓아지는 형식이다. 

이렇게 표현한다면 순열 형식으로 1) 같은 행 2) 같은 열이 아닌 모든 경우의 수를 찾을 수 있다.

대각선은 x1열 y1행과 x2열 y2행의 자리가 있다면, (x1 - x2의 절대값)과 (y1 - y2의 절대값)이 같은 경우로 확인할 수 있다.

 

* 코드

import java.util.Scanner;

public class Main {
	static int N;
	static int queen[];
	static int cnt;
	static boolean isSelected[];
	
	static boolean check(int r, int i) { // r번째 행 i번째 열
		for (int k=0; k<r; k++) { // k행 queen[k]열의 퀸과 비교
			// 대각선에 걸리는 경우 false
			if (Math.abs(k-r)==Math.abs(i-queen[k])) return false;
		}
		return true; // 써도 됨
	}
	
	static void findQueen(int r) {
		if (r==N) { // N개를 모두 찾았을 경우 종료
			cnt++;
			return;
		}
		
		for (int i=0; i<N; i++) {
			if (isSelected[i] || !check(r, i)) continue; // 이미 선택되었거나, 대각선 겹치면 X
			queen[r] = i; // r번째 행 i번째 열
			isSelected[i] = true; // 선택 체크
			findQueen(r+1);
			isSelected[i]=false; // 선택 해제
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// 입력 및 초기화
		N = sc.nextInt();
		queen = new int [N];
		isSelected = new boolean[N];
		
		// 퀸 개수 찾기
		findQueen(0);
		
		// 출력
		System.out.println(cnt);
		sc.close();
	}

}