백준 9663번: N-Queen

문제 설명

• NxN 체스판에 N개의 퀸을 놓는 경우의 수를 구하는 문제입니다.

접근법

• N의 값이 14까지 가능하기 때문에 완전탐색의 경우 시간초과가 납니다.
  • 가능한 총 경우의 수 -> $n*nCn$
• 백트래킹을 통해 불가능한 경우의 수를 제거하는 방향으로 문제를 풀어야 합니다.
• 실제 경우의 수와 유사한 방법은 2차원 배열이지만, 퀸은 같은 행 또는 같은 열에 존재할 수 없습니다. 이를 이용해 1차원 배열에서 가능 여부를 체크할 수 있습니다.
  • 1차원 배열에 나타냈지만 대각선을 판별하기 위해 퀸들의 x좌표값과 y좌표값을 모두 알고 있어야 합니다.
• 저는 배열의 인덱스를 col, 배열의 값을 row로 두었습니다.
  • 이를 통해 1차원 배열에서 x좌표와 y좌표를 모두 표현할 수 있게 되었습니다.
  • 체스의 좌표를 (0,0)부터 시작하게 되면 배열에 있는 0이 좌표값 0인지 초기값 0인지 구별할 수 없습니다. 그래서 N+1크기의 배열을 만들었습니다.
  • array[3] = 8은 (8,3)에 퀸을 두겠다는 의미입니다.

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;
	}

}

기타

틀린 이유

• 접근법 자체를 잘 떠올리지 못했습니다.
• 배열의 길이를 N으로 두고 (0,0)부터 시작해 틀렸었습니다.
• 각 변수(r,c,i,...)들이 무엇을 의미하는지가 헷갈려 문제를 푸는데 오랜 시간이 걸렸습니다.