백준 9633 N-Queen
N-Queen 문제
N x N 크기의 체스판에 N 개의 퀸 끼리 서로 공격할 수 없도록 배치하는 경우의 수를 계산하는 문제이다.
•
퀸은 가로 세로 대각선으로 이동이 가능하다.
구현은 어떻게 해야할까?
각각의 열과 행을 다 조사하면 시간 초과가 날 것이다. 따라서 행을 기준으로 탐색을 한다.
•
이때 그래프의 모든 행을 for 문 순회 하는것이 아니다.
행을 기준으로 잡고 열을 순회 하면서 해당 자리가 퀸이 존재할 수 있는 자리인지 판단한다. 이때 한단 기준은 아래와 같다.
•
해당 자리가 이전 퀸과 같은 열인가?
•
해당 자리가 이전 퀸의 대각선 자리에 위치하는가?
조건을 만족하는 경우 아래와 같이 압축한 행에 퀸을 넣을 것이다.
•
만약 N = 3 인 경우,
위와 같이 생긴 그래프를 아래와 같이 압축한다.
•
만약 그래프에 수가 모두 채워지면 해 중 하나라는 소리이므로, count 를 올려 준다.
문제 풀이
package baekjoon.level.gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class PROB9663 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N;
static int[] row;
static int count;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
row = new int[N];
count = 0;
solve(0);
System.out.println(count);
}
public static void solve(int n) {
if (n == N) {
count++;
return;
}
for (int i = 0; i < N; i++) { // 행 체크
if (checkPromising(n, i)) {
row[n] = i;
solve(n + 1);
}
}
}
public static boolean checkPromising(int n, int col) {
for (int i = 0; i < n; i++) {
if (row[i] == col || Math.abs(row[i] - col) == Math.abs(i - n)) { // 열 체크, 대각선 체크
return false;
}
}
return true;
}
}
Java
복사