[백준/boj] 9663: N-Queen (Java) / 백트래킹

문제

9663번: N-Queen

풀이

import java.io.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N;
	static int[] col; 
	static int answer = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		col = new int[N+1]; // 퀸이 놓이는 열 (size: 행의 수)
		setQueen(0);
		System.out.println(answer);
	}

	private static void setQueen(int row) {
		if(!isValid(row)) { // 유효하지 않은 경우, return(백트래킹, 가지제거)
			return; 
        }
		
        if(row == N) { // 모든 행에 퀸을 둔 경우 
			answer++; // 답 증가
			return;
		}
        
		for(int i=1; i<=N; i++) { // 1 열 N 열까지
			col[row+1] = i; // row가 0일 때, 1행의 1열에 퀸을 위치하는 경우의 수부터 N열에 위치하는 경우의 수까지,
			setQueen(row+1); // 행 + 1 (가지를 늘려나간다.)
		}
	}

	private static boolean isValid(int row) {
		for(int i=1; i< row; i++) { // 1행부터 row -1행까지 (row 이전 행에 이미 퀸을 위치시킨 상태)
        	// 같은 열에 퀸이 존재하거나 || 대각선(열의 차이의 절댓값 == 행의 차이)에 위치한 경우 false return
			if(col[row] == col[i] || Math.abs(col[row]-col[i]) == row-i) return false;
		}
		return true;
	}
}

 

퀸이 위협하는 자리는 같은 행, 같은 열, 대각선 위치 이다. 

같은 행에는 놓을 수 없기 때문에 1차열 배열(col[row]) 을 사용했다. 행(row)에 놓이는 퀸의 열(col) 값을 담는다.

퀸을 놓는 경우의 수는 대표적인 백트래킹의 예제이다.

백트래킹은 경우의 수 가지들이 뻗어나갈 때, 유망하지 않은 가지들은 제거하면서 전체 탐색을 하는 것으로, 재귀가 많이 쓰인다.

이 예제에서 가지를 제거하는 조건은, 같은 열에 퀸이 존재하거나, 대각선에 위치한 경우이다.