[백준(Baekjoon)][자바(java)] 9663 : N-Queen / 백트래킹

 

www.acmicpc.net/problem/9663

9663번: N-Queen

 

입력 

N  ( 1 ≤ N < 15 )

 

출력

크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수

 

풀이

 

▷  분기한정법  ( 더 빠름 )

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

public class Main {
	
	static int n, cnt, pos[];
	static boolean[] v_col, v_diag1, v_diag2;

	public static void nqueens(int row) {
		if (row == n) {
			cnt++;
			return;
		}
		for (int col = 0; col < n; col++) {
			if (v_col[col] == false && v_diag1[row + col] == false && v_diag2[row - col + (n - 1)] == false) {
				pos[row] = col;
				v_col[col] = v_diag1[row + col] = v_diag2[row - col + (n - 1)] = true;
				nqueens(row + 1);
				v_col[col] = v_diag1[row + col] = v_diag2[row - col + (n - 1)] = false;
			}
		}
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		br.close();

		pos = new int[n]; 						// 각 row에 놓여지는 col의 idx
		v_col = new boolean[n]; 				// 열 방문 여부
		v_diag1 = new boolean[2 * n - 1]; 	// 대각선1 방문 여부
		v_diag2 = new boolean[2 * n - 1]; 	// 대각선2 방문 여부

		nqueens(0);

		System.out.println(cnt);
	}
}

출처 : 「 DoIt 자료구조와 알고리즘 자바편 」

( 백트래킹을 개선한 기법인 분기 한정법 )

 

▷  백트래킹

import java.io.*;

public class Main {

	static int n, cnt, cols[]; // col : 각 row에 놓여지는 col의 idx

	public static void nqueens(int row) {
		if (!promising(row))
			return;
		else if (row == n) {
			cnt++;
			return;
		}
		for (int col = 1; col <= n; col++) {
			cols[row + 1] = col;
			nqueens(row + 1);
		}
	}

	public static boolean promising(int row) {
		for (int col = 1; col < row; col++) 
			if ((cols[col] == cols[row]) || (row - col == Math.abs(cols[row] - cols[col])))
				return false;
		return true;
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		br.close();

		cols = new int[n + 1];

		nqueens(0);

		System.out.println(cnt);
	}
}