💔 9663 N-Queen java

문제 설명

https://www.acmicpc.net/problem/9663

1. N*N 체스판이 주어진다.
2. 체스판에 Queen을 서로가 서로를 죽이지 못하게 모든 행에 놓아라
3. 이떄 놓을 수 있는 경우의 수는 어떻게 되는가?

푸는 원리

백트래킹을 사용해야 한다. 백트래킹이란 깊이 우선 탐색을 하되, 가능성이 없는 루트를 탐색한다고 판단될 경우 과감하게 그 루트를 포기하고 다음 경우의 수를 체크하러 떠나는 것이다.
해당 길이 답을 도출할 수 있는 유망한 길인지 아닌지 체크하는 것은 문제마다 다르다. 따라서 유망성 체크 조건을 알아차리는 감각은 많은 백트래킹 문제를 풀어보며 익혀야 하겠다.

본론으로 돌아와서 N-Queen 문제를 풀어보자.
체스에서 퀸은 비숍과 록을 합친 움직임을 할 수 있는 가장 쎈 장기말이다. 따라서 4방향의 대각선과 위, 아래 모두 갈 수 있다.

생각해야할 모든 경우의 수에 대해서 일단 생각해보자. 행을 x, 열을 y라고 해보자

1. 같은 행(가로) 체크: 한 행씩 퀸을 놓는 것은 당연하다. 1행에 하나의 퀸을 놓으면 바로 2행으로 넘어가는 식으로 반복문을 짠다면, 해당 경우는 따로 체크할 필요가 없다.
2. 같은 열(세로) 체크: 세로 체크는 무조건 필요하다. 이전 행에서 놨던 퀸이 현재 퀸 놓으려는 자리와 겹치는 지 확인을 해야한다.
3. 좌하단 - 우상단 체크: 노 다웃으로 필요하다.
4. 좌상단 - 우하단 체크: 이것도 무조건 필요하다.

따라서 위 결과 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;
            }
        }

    }
}