[백준] 9663. N-Queen (자바 JAVA)
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8
예제 출력 1
92
접근 방법 🧐
백트래킹으로 풀어본다.
배열을 이용한 상태 표현
arr[depth]를 통해 depth번째 행에 놓인 퀸의 열 위치를 저장하고
한 행에 하나의 퀸만 배치하기 때문에 arr 배열로 간단히 표현 가능.
행(depth)을 기준으로 퀸을 한 줄씩 배치해 나가면서 모든 가능한 경우를 탐색한다.
DFS(depth)는
1. 현재 depth 행에서 퀸을 배치하고 다음 행으로 진행하고,
2. 같은 열(arr[depth] == arr[j])에 퀸이 있는지 확인한다.
3. 대각선(Math.abs(depth - j) == Math.abs(arr[depth] - arr[j]))에 퀸이 있는지 확인한다.
위 조건을 모두 만족하면 유효한 배치로 간주하고 다음 행으로 진행한다.
이 과정을 반복해서 depth == N이면 모든 퀸이 배치된 경우로 간주하여 count를 1씩 증가시킨다.
유효하지 않은 배치는 continue해서 불필요한 연산을 줄인다.
시간 복잡도는 최악의 경우 𝑂(𝑁!) (N개의 행에 각각 1개의 퀸을 배치하는 모든 경우)가 되는데,
백트래킹으로 풀면 대각선 그리고 같은 열 조건으로 많은 가지치기가 이루어지므로
시간 복잡도는 𝑂(𝑁!)보다 훨씬 작게 된다.
내가 쓴 코드 ✍️
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int N, count = 0;
private static int[] arr;
private static void DFS(int depth) {
if (depth == N) {
count++;
return;
}
for (int i = 0; i < N; i++) {
arr[depth] = i;
boolean isValid = true;
for (int j = 0; j < depth; j++) {
if (arr[depth] == arr[j] || Math.abs(depth - j) == Math.abs(arr[depth] - arr[j])) {
isValid = false;
break;
}
}
if (isValid) {
DFS(depth + 1);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
DFS(0);
System.out.println(count);
}
}
후기
체스 게임의 규칙을 알면 풀기 수월할 것이다.