https://www.acmicpc.net/problem/9663
백트래킹에서 가장 유명한 문제이다
백트래킹의 정석문제이다.
모든 경우를 따져본다는 점에서 좋은 문제.
가지치기의 개념을 공부하기도 적합함
발상의 전환도 필요한 문제이다.
분명 2차원 배열의 정사각형에서 퀸을 서로 공격할 수 없는 위치에 나열하는 것이 문제이다.
하지만, 생각해보면, 1차원 배열만을 가지고도 경우의 수는 계산할 수 있다.
public static void DFS(int depth) {
if (depth == N) {
// 모든 조건을 통과한 경우,
// 경우의 수를 증가.
numberOfCases++;
return;
}
for (int i = 0; i < N; i++) {
arr[depth] = i;
// 유망성 체크가 true일 경우, 가지치기를 하지 않고 계속해서 진행
if (isPossibleCheck(depth)) {
DFS(depth + 1);
}
}
} // End of DFS
아래의 for문에서 depth
재귀의 깊이를 index로 사용해서 i
를 넣는다.
이 과정이 곧, 2차원 배열에서 열과 행에 퀸을 놓는 작업인데,
index
== depth
(열) 에
i
== value(행) 위치에 퀸을 놓는다고 표현할 수 있다.
이후 퀸을 하나 놓은 후에는 곧바로 유망성 체크를 한다. 현재 퀸을 놓은자리에 공격위치와 겹치는 퀸이 있는지 없는지를 체크하고, 모든 퀸이 공격위치에 겹치지 않아서 depth
가 N
과 같아질 경우, 재귀 종료 조건에 해당해서 경우의 수 인 numberOfCases
를 1증가한다.
이 과정을 반복해서 모든 경우의 수를 도출 할 수 있다.
for (int i = 0; i < colNum; i++) {
// 같은 행에 위치한 퀸이 있는
if (arr[colNum] == arr[i]) { // 하나라도 겹치는 값이 있으면 중지
return false;
}
// 대각선 체크
// 대각선은 열의 값 차이와 행의 값 차이가 같을 경우 같은 대각선 상에 있게된다.
if (Math.abs(arr[colNum] - arr[i]) == Math.abs(colNum - i)) {
return false;
}
}
유망성 체크는 하나의 체스가 판에 올라왔을 때 체크를 하게 되는데,
현재 올라온 퀸이 지금까지 올라온 퀸과 공격이 겹치는 지를 체크하게 된다.
체크는 2가지를 하는데,
첫 번째는 가로 세로로 일치하는가 즉, 같은 행에 퀸이 현재 위치하는가를 파악한다.
두 번째는 대각선으로 겹치는가 이다.
먼저 가로 세로는 위에서 설명과 같이 index
가 열이고 value가 행이기 때문에 같은 다른 index
임에도 불구하고 같은 value를 가지는 index
가 있다면 공격이 겹치는 것이기때문에 곧바로 false를 return 한다.
다음은 대각선인데, 대각선은 규칙이 있다. 열의 위치 차이값의 절댓값과, 행의 차이 절댓값이 같을 경우, 대각선 상에 있음을 알 수 있다.
이 2가지 조건중 하나라도 만족하게 된다면 우리는 해당 위치에 퀸을 놓을 수 없다.
import java.io.*;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, ans;
private static int[] comb;
private static boolean[] isVisited;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
DFS(0);
sb.append(ans);
return sb.toString();
} // End of solve()
private static void DFS(int depth) {
if (depth == N) {
ans++;
return;
}
for (int i = 0; i < N; i++) {
comb[depth] = i;
if (isAbleCheck(depth)) {
DFS(depth + 1);
}
}
} // End of DFS()
private static boolean isAbleCheck(int depth) {
for (int i = 0; i < depth; i++) {
if (comb[i] == comb[depth]) {
return false;
}
if (Math.abs(comb[depth] - comb[i]) == Math.abs(depth - i)) {
return false;
}
}
return true;
} // End of isAbleCheck()
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
comb = new int[N];
isVisited = new boolean[N];
} // End of input()
} // End of Main class