백준 9663 N-Queen 자바

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

9663번: N-Queen

 

못 풀어서 답을 봤다. 코드는 간단하지만 생각하기 쉽지 않은 문제다.

 

 

접근 방식

단순하게 2차원 배열을 생성하고 모든 경우의 수를 계산하려고 했다. 퀸을 놓은 후 재귀 탐색을 설정하는데 어려움을 겪었었다. 정답을 보고 이해한 뒤에 며칠 뒤 다시 풀어보니 잘 풀렸다.

 

 

퀸을 놓을 수 있는지 확인할 때는 1차원 배열이면 충분하다. 가로와 세로 같은 열에 퀸을 놓을 수 없으니 1차원 배열에 row값을 삽입하고 다음 번 놓을 퀸이 이전의 row값들과 같은 값이 있다면 false를 리턴한다.

대각선의 경우 따로 공식이 있다. 

 

rowNo-i == Math.abs(col[rowNo] - col [i])

 

그림을 그려서 이해하면 공식이 이해가 간다. 

 

 

for문을 처음부터 탐색해서 1차원 배열에 i값을 삽입한다. 다음번 퀸을 놓을 수 있는지 isAvailable함수로 체크하고 놓을 수 있다면 다음 번 퀸을 재귀 탐색한다. 중간에 return된다면 다음 row에 값을 넣고 다시 재귀탐색한다.

 

배열에 값은 {1,3,5,2,6,7,8} 이렇게 담길 것이다.

 

 

 

import java.util.Scanner;

public class NQueenBackTracking2 {

	static int N, ans;
	static int col[];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		col = new int[N+1];
		ans = 0;
		setQueen(1); //첫 퀸은 무조건 넣을 수 있으므로 1부터 진행하며 안그런 경우 1을 넣기전에 available로 체크해야함
		System.out.println(ans);
		
	}
	
	static void setQueen(int rowNo) { // rowNo : 퀸을 두어야하는 현재 행
		
		
		//기저조건 퀸을 다 놓은 경우 - rowNo는 1부터 시작이므로 n보다 커야함
		//기저조건에 도착하면 바로 답인 이유는 답이 아닌 경우 가지치기로 사전에 체크함
		if(rowNo>N) {
			ans++;
			return;
		}
		
		//1열부터 n열까지 퀸을 놓는 시도
		for (int i = 1; i <= N; i++) {
			col[rowNo] = i;
			if(isAvailable(rowNo)) { //여기까지 가능했다면 이다음퀸이 가능한지 체크
				setQueen(rowNo+1);
			}
		}
		
	}
	
	static boolean isAvailable(int rowNo) { // 아까놓은 퀸 직전까지 퀸을 놓을 수 있는지 비교해야함 rowNo : 놓아진 마지막 퀸
		
		for (int i = 1; i < rowNo; i++) {
			if(col[rowNo] == col[i] || rowNo-i == Math.abs(col[rowNo] - col[i])) return false; //현재놓은 퀸 rowNo과 기존에 놓은 퀸 i 가 같은경우
		}
		return true;
	}
}