白駿9663号:N-Queen

問題の説明

方法

d[r]=cまたはd[c]=rがコアであることを考え続けます。

正解

import java.util.*;

public class Main {
	static int[] array;
	static int N;
	static int cnt;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		array = new int[N+1]; // 인덱스는 col, 값은 row를 나타내는 array배열을 만듬 //0을 idx로 사용하면 0값과 초기값0이 있어 비교가 어려워짐
		cnt = 0;
		BackT(1);
		System.out.println(cnt);
	}
	
	public static void BackT(int c) {
		if(c > N) { // array배열을 모두 다 채웠다는 의미입니다.
			//System.out.println(Arrays.toString(array));
			cnt++;
			return;
		}
		
        // 1부터 N까지 순회합니다.(배열을 한칸 더 크게 만들었기 때문에)
		for (int i = 1; i <= N; i++) { // i는 row값입니다.
			if(!validate(i,c)) continue; //(i,c)칸에 퀸을 두는 게 잘못되었다면 더 이상 해당 경우의 수에서 퀸을 찾지 않습니다.(해당 가지를 잘라냅니다)
            //여기가 실행된다는 것은 validate를 통과했다는 의미입니다.
			array[c] = i; // (i,c)칸에 퀸을 두겠다는 의미입니다.
			BackT(c+1); // 다음 퀸을 찾으러 갑니다.
			
		}
		
	}
	
	public static boolean validate(int i,int c) { 
		for (int j = 1; j < c; j++) { // j는 이전까지 제가 두었던 퀸의 column값입니다. 
        	// 이전에 두었던 퀸들과 비교해 봅니다.
            // row값이 같거나, 대각선으로 겹친다면 입력값으로 들어온 (i,c)는 잘못된 값입니다.
            // 우리는 column의 값을 1씩 증가시키면서 백트래킹을 실행하고 있기 때문에 column은 비교할 필요가 없습니다.(당연히 다르다는 말입니다.)
			if( array[j] == i || Math.abs(array[j]-i) == Math.abs(j-c) ) {
				return false;
			}						
		}
		return true;
	}

}

その他

まちがった理由