문제 설명
https://www.acmicpc.net/problem/9663
- N*N 체스판이 주어진다.
- 체스판에 Queen을 서로가 서로를 죽이지 못하게 모든 행에 놓아라
- 이떄 놓을 수 있는 경우의 수는 어떻게 되는가?
푸는 원리
백트래킹을 사용해야 한다. 백트래킹이란 깊이 우선 탐색을 하되, 가능성이 없는 루트를 탐색한다고 판단될 경우 과감하게 그 루트를 포기하고 다음 경우의 수를 체크하러 떠나는 것이다.
해당 길이 답을 도출할 수 있는 유망한 길인지 아닌지 체크하는 것은 문제마다 다르다. 따라서 유망성 체크 조건을 알아차리는 감각은 많은 백트래킹 문제를 풀어보며 익혀야 하겠다.
본론으로 돌아와서 N-Queen 문제를 풀어보자.
체스에서 퀸은 비숍과 록을 합친 움직임을 할 수 있는 가장 쎈 장기말이다. 따라서 4방향의 대각선과 위, 아래 모두 갈 수 있다.
생각해야할 모든 경우의 수에 대해서 일단 생각해보자. 행을 x, 열을 y라고 해보자
- 같은 행(가로) 체크: 한 행씩 퀸을 놓는 것은 당연하다. 1행에 하나의 퀸을 놓으면 바로 2행으로 넘어가는 식으로 반복문을 짠다면, 해당 경우는 따로 체크할 필요가 없다.
- 같은 열(세로) 체크: 세로 체크는 무조건 필요하다. 이전 행에서 놨던 퀸이 현재 퀸 놓으려는 자리와 겹치는 지 확인을 해야한다.
- 좌하단 - 우상단 체크: 노 다웃으로 필요하다.
- 좌상단 - 우하단 체크: 이것도 무조건 필요하다.
따라서 위 결과 2,3,4번은 서로 같은 선상에 있는지 체크를 해줘야 한다는 것을 알았다. 그렇다면 어떻게 구현할 것인가. 먼저 2,3,4,번 각 경우에 대한 방문 배열을 만든다. 밑의 사진을 보라
2번의 경우 그냥 하나의 행에 대한 방문 배열을 만들면 된다. 예를 들어 (0.0)을 썼다면,
| 1열 | 2열 | 3열 | 4열 |
|---|---|---|---|
| T | F | F | F |
1열은 이제 못 쓰는 의미로 T로 바꾼다.
3번,4번의 대각선 경우는 수학적 생각이 조금 필요한데, 위의 사진을 보고 밑줄 친 행렬마다 어떠한 공통점을 가진다는 것을 생각 해야한다. 혹시 보이는 게 없는가?
3번의 경우 (노란색 형광펜)은 x+y 가 같은 녀석들의 집합이다. 따라서 방문 배열을 x+y의 값으로 만든다.
| x+y = 1 | x+y = 2 | x+y = 3 | x+y = 4 | x+y = 5 | x+y = 6 |
|---|---|---|---|---|---|
| F | T | F | T | F | F |
만약 다음과 같이 방문 배열이 되어있다면, x+y가 2인 대각선과 4인 대각선은 이미 사용해서 사용 못한다는 의미이다.
4번의 경우도 3번과 원리는 똑같은 4번의 파란색 형광펜의 공통점은 x-y가 같은 행렬끼리 같은 노선 위에 있다는 점이다. 근데 저 사진에서도 알 수 있듯이 -3 ~ +3 식으로 마이너스인 부분이 존재한다. 배열의 index로 음수가 올 수 없으므로, 해당 값이 0부터 시작하도록 적절한 값을 더한다. (나는 N+1을 더했다.)
그 후 위 3개의 방문 배열을 이용해서, 체스판 좌표 (x,y)가 유효한지 DFS로 계속 검증해나가면 된다.
밑은 코드이다.
코드분석
import java.util.*;
import java.io.*;
public class Main {
// N-Queen 문제
// : 체스 퀸을 서로 공격하지 못하는 장소로 놔둬라
static int N;
// N퀸 성공한 경우의 수
static int cnt;
// 열 체커
static boolean [] isVisitedX;
// 오른쪽 대각선 체커
static boolean [] isVisitedR;
// 왼쪽 대각선 체커
static boolean [] isVisitedL;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
isVisitedX = new boolean[N];
isVisitedR = new boolean[2*N];
isVisitedL = new boolean[2*N];
recur(0);
System.out.println(cnt);
}
// x는 행, y는 열
public static void recur( int x) {
if(x== N){
cnt++;
}
// i는 열번호
for (int i = 0; i < N; i++) {
// 만약 하나라도 못 지키면, 다음 i를 봐야함. (방문 배열 true, false 값 건드리면 안된다.)
// 열 체킹
if(!isVisitedX[i]) {
isVisitedX[i] = true;
// 왼 하단 -> 우 상단 체킹
if(!isVisitedR[i+x]) {
isVisitedR[i+x] = true;
// 오 하단 -> 왼 상단 체킹
if(!isVisitedL[i-x +(N-1)]) {
// 체크 모두 성립하면 다음 재귀로 넘어감
isVisitedL[i-x +(N-1)] = true;
recur(x+1);
isVisitedL[i-x +(N-1)] = false;
}
isVisitedR[i+x] = false;
}
// 재귀에서 나와선 아까 체크 했던 것 모두 원 상 복귀
isVisitedX[i] = false;
}
}
}
}