..백트래킹이라는 개념을 이번 강의를 통해 처음 접했는데,
나랑 안맞는 것 같다 ㅎ..
우선 이 문제는 이번 주의 강의였던
[바킹독의 실전 알고리즘] 0x0C강 - 백트래킹
에 있던 예제 중 하나였다.
물론 강의는 c++로 되어있으나, 우리는 자바로 문제를 풀기에
강의 내용을 이해한 후 자바로 재해석하여 문제를 해결하였다.
package test11;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Ox11_Q3_1 {
static int cnt = 0; // 경우의 수
static int n;
static boolean issued1 [] = new boolean [30]; // 세로 열 체크
static boolean issued2 [] = new boolean [30]; // 오른쪽 위 대각선 체크
static boolean issued3 [] = new boolean [30]; // 오른쪽 아래 대각선 체크
// 백준 9663 G4 N-Queen
public static void main(String args []) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
checkFunc(0);
System.out.println(cnt);
}
public static void checkFunc(int cur) {
// 체스 놓은 말 개수가 n이랑 같으면 return
if (cur == n) {
cnt++;
return;
}
for (int i = 0; i < n; i++) {
// Q가 있는 열, 오른쪽 대각선, 왼쪽 대각선에 값이 있는 경우 continue;
if (issued1[i] || issued2[i + cur] || issued3[cur - i + n - 1]) {
continue;
}
// 세 곳 값 세팅
issued1[i] = true;
issued2[i + cur] = true;
issued3[cur - i + n - 1] = true;
// 재귀
checkFunc(cur + 1);
// 다 놓아본 후 새로 복원
issued1[i] = false;
issued2[i + cur] = false;
issued3[cur - i + n - 1] = false;
} // for fin
}
}
처음에 예제를 볼때, 왜 1차월 배열로 값을 체크하지? 하는 생각이 들었다.
제대로 이해가 되지 않았었으나, 구글링을 통해 해당 개념을 어느정도 이해할 수 있었다.
문제 특성상 체스를 한 개 두면 해당 열과 행 모두 둘 수 없기에 위에서 보면 하나의 열에 하나씩
값이 들어가 있는 느낌이다. 즉 배열 한 개가 있을 때 해당 인덱스가 열이고, 그 안에 있는 각각의 값이 행을 의미한다고
해석하면 된다.
다음으로, 함수 checkFunc를 해석해 보겠다. 체스를 말을 놓은 개수 cnt를 인자로 받고있다.
만약 (0,0) 에 퀸을 둔다고 가정하면 이에 해당 하는 x열, x행, 대각선 방향은 모두 값을 놓을 수 없으므로
이를 손쉽게 체크하기 위해 배열 세개를 두어 간편하게 검증하였다.
이후 해당 x열 (인덱스)를 의미하는 isuued1
해당 x열의 오른쪽 대각선 증가 를 의미하는 issued2
해당 x열의 왼쪽 대각선 감소를 의미하는 isuued3 에 각각 true값을 준 후 반복하여 해당 경우의 수를 구해고,
만약 재귀문이 종료되면 해당 구문들을 다시 false로 초기화해준다.
문제 자체는 어려웠으나, 강의 덕분에 차근차근 따라하여 수월하게 해결하긴했다.
하지만, 앞으론 혼자서도 해결할 수 있어야하므로 이에 방심하지 않고 꾸준히 공부해야겠다.
