[BOJ 9663] N-Queen

문제

---

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력으로 첫째 줄에 N이 주어진다. (1 <= N <= 15)
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

[풀이 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int N, count;
	static boolean[][] v;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		count = 0;
		v = new boolean[N][N];
		dfs(0);

		System.out.println(count);
	}
	private static void dfs(int r) {
		
		if(r==N) {
			count++;
			return;
		}
		for (int c = 0; c < N; c++) {
			if(isPossible(r, c)) {
				v[r][c] = true;
				dfs(r+1);
				v[r][c] = false;
			}
		}
	}
	
	static int[] p_dr = {-1, -1, -1};
	static int[] p_dc = {0, -1, 1};
	private static boolean isPossible(int r, int c) {
		for (int d = 0; d < p_dr.length; d++) {
			int nr = r;
			int nc = c;
			while(true) {
				nr+=p_dr[d];
				nc+=p_dc[d];
				if(nr<0 || nr>=N || nc<0 || nc>=N) break;
				if(v[nr][nc]) return false;
			}
		}
		return true;
	}
}

백트래킹 문제다.

퀸을 하나 놓고, 그 다음 위치로 이동할 때, 퀸이 서로 공격할 수 없는 위치에 놓아야 한다.
이를 위해서 공격할 수 있는지 없는지 체크해주는 isPossible 메서드를 만들었다.
하지만, 처음에는 p_dr, p_dc 배열 변수를 팔방탐색으로 해서 시간초과가 났다.
퀸은 (0, 0) 부터 한 줄씩 아래로 내려가며 놓기 때문에, 현재 행 위쪽 방향만 탐색해도 충분하다.
즉, 위(-1, 0), 왼쪽 위(-1, -1), 오른쪽 위(-1, 1) 이 3가지 방향만 고려하면 된다.