[백준] 9663 - NQueen

[문제링크]

9663번: N-Queen

 

0. 백트래킹의 국룰문제

 

1. n번째 행에 대해 1~n-1행의 퀸 위치와 충돌하지 않는 모든 열들을 놓아보면서 진행한다

 

2. 모든 행에 성공적으로 퀸이 놓아졌다면 성공 카운트 + 1

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		
		pos = new int[N];
		ans=0;
		
		rec(0);
		System.out.println(ans);
		
	}
	static int ans;
	static int[] pos;
	
	static void rec(int row) {
		if(row==pos.length) {
			ans++;
			return;
		}
		
		for (int i = 0; i < pos.length; i++) {
			if(isOK(row, i)) {
				pos[row]=i;
				rec(row+1);
			}
		}
	}

	static boolean isOK(int row, int i) {
		for (int j = 1; j <= row; j++) {
			if(pos[row-j]==i)return false;
			if( Math.abs(pos[row-j]-i) == j)return false;
		}
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면