백준 9663번
https://www.acmicpc.net/problem/9663
문제
생각하기
-
백트래킹에서 가장 유명한 문제이다
-
백트래킹의 정석문제이다.
-
모든 경우를 따져본다는 점에서 좋은 문제.
-
가지치기의 개념을 공부하기도 적합함
- 퀸 하나를 놓고, 다른 곳에 퀸을 놨을 때, 겹칠 경우, 해당 경우는 배제하는 상황이 가지치기 개념임. (유망성 체크)
-
-
발상의 전환도 필요한 문제이다.
-
분명 2차원 배열의 정사각형에서 퀸을 서로 공격할 수 없는 위치에 나열하는 것이 문제이다.
-
하지만, 생각해보면, 1차원 배열만을 가지고도 경우의 수는 계산할 수 있다.
- 배열에서 index값을 열로 나타내고, index에 들어가있는 값을 행으로 표현하면 된다.
- 예시로 들자면 N이 4일 때, [1, 2, 3, 4]의 경우에는 1열 1행에 퀸이 있다는 뜻이고, 2열 2행에 퀸이 있다는 의미에 해당한다.
-
동작
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증가한다.
이 과정을 반복해서 모든 경우의 수를 도출 할 수 있다.
2.
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가지 조건중 하나라도 만족하게 된다면 우리는 해당 위치에 퀸을 놓을 수 없다.
코드
Java
import java.io.*;
public class Main {
static int N;
static int[] arr;
static int numberOfCases;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
numberOfCases = 0;
// N*N의 배열에서
// 조합을 만들 때 굳이 2차원 배열을 만들 필요가 없다.
// 배열의 인덱스값은 열의 번호를 나타내고, 배열의 원소의 값은 행 번호를 의미하게 나타내면 모든 경우의 수를 만들 수 있다.
arr = new int[N];
DFS(0);
System.out.print(numberOfCases);
} // End of main
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
public static boolean isPossibleCheck(int colNum) { // 유망성을 체크하는 메소드
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;
}
}
return true;
} // End of isPossibleCheck
} // End of Main class
