[백준] 9663 N-Queen (Java)

백준 9663 N-Queen

문제

---

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

입력

---

첫째 줄에 N이 주어진다 (1<=N<=15)

출력

---

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다

예제 입력 1

---

8

예제 출력 1

---

92

풀이

---

백트래킹 문제다.

체스에서 퀸은 상하, 좌우, 대각선으로 끝까지 공격할 수 있다.
그렇기 때문에 퀸 N개가 서로 공격할 수 없도록 놓기 위해서는 한 행(또는 한 열을 기준으로 잡아도 됨)에 퀸을 한 개 놓을 수 있다.




행을 기준으로 잡았을 때(백트래킹에서의 depth) 1차원 배열 map의 인덱스가 행이 되고 해당 인덱스의 값이 열이 된다.

0행부터 열 값을 대입하고 그 대입이 규칙에 맞는 지 판별하는 방법은 다음과 같다.
1. 모든 다른 행과 열 값이 같으면 안된다
2. 모든 다른 행과 대각선에 있으면 안된다

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_Q9663_NQueen {
	public static int n;
	public static int cnt =0;
	public static int[] map;
	// 다른 퀸 위치의 공격을 받을 수 없는 위치인지 판별
	public static boolean isPossible(int index) {
		for(int i=0; i<index; i++) {
			// 다른 퀸과 같은 열에 위치하지 않는 지
			if(map[index] == map[i]) {
				return false;	
			}
			// 다른 퀸의 대각선에 위치하지 않는 지
			if(Math.abs(map[index]-map[i])== Math.abs(index-i)) {
				return false;
			}
		}
		return true;
	}
	public static void backTracking(int index) {
		// 모든 행에 퀸을 배치했다면
		// 경우의 수 추가
		if(index == n) {
			cnt++;
			return;
		}
		// 행, 열 값 
		for(int i=0; i<n; i++) {
			map[index] = i;
			if(isPossible(index))
				backTracking(index+1);
		}
	}
	public static void main(String[] args) throws IOException, NumberFormatException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n];
		backTracking(0);
		System.out.println(cnt);
	}
}