NQueen 문제 해결하기 Java

아무래도 백트래킹 문제가 약한거 같아서 GTP 에게 문제를 좀 내달라고 했다.

 

 

쉬운 문제 2개는 부분 수열의합 문제와 모든 순열 출력하기를 내줬고, 이는 백준에서 풀었던 문제와 비슷해서 복습하는 개념으로 풀었다. 그리고 중간 나이도 문제로 N Queen 문제를 내줬다.

 

문제

 

 

해결하기

 

재귀 호출 설계

재귀를 잘못 설계하면 Stackoverflow 에 빠질 수 있다. NQueen 경우의 수를 구하는 문제일 때 재귀 횟수를 줄이려면 다음과 같이 해야한다.

 

(1) 하나의 기준을 정하고 순회한다.

'각 퀸이 서로 공격할 수 없다.' 라는 조건에 따라 Row, Col 을 기준으로 하나의 queen 을 넣을 수 있나? 만 고려하면 되고 그렇게 되면 순회 횟수가 N*N 에서 N 으로 줄어든다.

 

(2) 기준 에 따라 놓을 수 있는 경우만 재귀가 계속된다.

즉 Row 를 기준으로 순회할 경우 i 번째 Row 에서 어떤 Column 에도 Queen 을 놓을 수 없다면 해당 재귀를 끝내야 한다. 이렇게 하면 재귀 호출은 N * a (0 < a <= 1) 번으로 줄어들게 된다.

대각선 검사 조건

나는 어차피 위쪽 Row 에서부터 아래쪽 Row 로 순회하면서 재귀를 호출할 것이기 때문에 '오른쪽 위에서 왼쪽 아래로 내려가는 대각선(right2Left)' 그리고 '왼쪽 위에서 오른쪽 아래로 내려가는 대각선(left2Right)' 만 검사하면 된다. 고민을 하면 이 구현이 생각보다 간단해진다.

 

right2left

Row 를 기준으로 위에서 아래로 내려간다. 그리고 0번째 Column 부터 N-1 번째 Column 을 순회하게 된다.

만약 {2, 1} 에 queen 을 놓았다고 해보자, 그렇다면 {3,0} 일때 right2left 조건은 false 를 반환해야한다.

 

아래의 표를 보자 각 row 와 col 값을 더했다.

{row, column} 일떄 {2, 1} 일때 3을, {3,0} 3을 나타낸다. 이러한 규칙에 의해 오른쪽 위에서 왼쪽으로 내려오는 대각선은 row + column  이 동일하다는 규칙을 발견할 수 있다. 이러한 규칙을 반영한 1차원 boolean 배열을 통해 right2Left 를 검증할 수 있다.

즉, 내가 조회하려는 row, col 을 이용해서 right2Left[row + col] == true 면 더이상 퀸을 놓을 수 없게 되는 것이다.

 

left2Right

비슷한 접근으로 해결된다. row - col 을 해보자

 

동일한 left 2 right 대각선상에 있는 값들은 같은 값을 띄고있다.

다만 이때는 index 가 음수가 나올 수 있으므로 이에 대한 조정이 필요하다. 

row - col의 최소값은 -(N - 1) 이다. 따라서 내가 조회하려는 row, col 에서 left2Right[row - col + N - 1] == true 면 더이상 퀸을 놓을 수 없게 되는 것이다.

 

이상의 내용을 코드로 만들어보자

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class NQueen {

    static int N, globalCount = 0;
    static boolean[] cols, right2Left, leftToRight;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        cols = new boolean[N]; // 각 열에 퀸이 놓였는지 체크
        right2Left = new boolean[2 * N - 1]; // 오른쪽에서 왼쪽 아래로 가는 대각선
        leftToRight = new boolean[2 * N - 1]; // 왼쪽에서 오른쪽 아래로 가는 대각선

        placeQueenAt(0);
        System.out.println(globalCount);
    }

    static void placeQueenAt(int row) {
        // 모든 행에 퀸을 놓았다면 경우의 수 증가
        if (row == N) {
            globalCount++;
            return;
        }

        // 현재 행의 모든 열을 탐색
        for (int col = 0; col < N; col++) {
            // 열, 대각선의 방문 여부 체크
            if (!cols[col] && !right2Left[row + col] && !leftToRight[row - col + N - 1]) {
                // 현재 위치에 퀸을 놓을 수 있다면
                cols[col] = true;
                right2Left[row + col] = true;
                leftToRight[row - col + N - 1] = true;

                // 다음 행으로 이동
                placeQueenAt(row + 1);

                // 백트래킹: 퀸을 제거
                cols[col] = false;
                right2Left[row + col] = false;
                leftToRight[row - col + N - 1] = false;
            }
        }
    }
}

 

삽질 하기

여기서부터 내 삽질을 기록해 놓은 것이기 때문에 굳이 확인할 필요는 없다.

 

예전에 42Seoul 에서 Pisine 과정에서 NQueen 문제를 풀었는데, 그때는 모든 체스판을 shallow copy 해서 풀었던 기억이 있다. 하지만 이제는 각 메서드를 재귀적으호 호출했을때 호출 stack 에 쌓이고 이것이 순차적으로 수행된다는것이 몸에 익었기 때문에 그냥 2차원 boolean 배열을 이용하기로 했다.

 

 

그래서 괴거 Pisine 과정에 비해 아주 조금 발전된 형태로 만든 내 코드는 아래와 같았다.

하지만 이 코드는 손쉽게 Stackoverflow 에 빠져버린다. 즉 재귀를 너무 많이 호출한다는 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class NQueen {
    static int N, globalCount = 0;
    static boolean[][] placed;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        placed = new boolean[N][N];
        placeQueenAt(0, 0);
        System.out.println(globalCount);
    }

    static void placeQueenAt(int pos, int nowCount) {
        if (nowCount == N) {
            globalCount++;
            return;
        }
        if (pos == N*N) {
            return;
        }

        int i0 = pos / N;
        int j0 = pos % N;

        placeQueenAt(pos + 1, nowCount); // 놓지 않은 경우

        if (check(i0, j0)) { // 놓을 수 있어서 놓은 경우
            placed[i0][j0] = true;
            placeQueenAt(pos + 1, nowCount+1);
            placed[i0][j0] = false; // 놓은 경우 초기화
        }
    }


    /**
     *
     * @param i0 현재 i 인덱스
     * @param j0 현재 j 인덱스
     * @return queen 을 놓을 수 있으면 true, 놓을 수 없으면 false
     */
    static boolean check(int i0, int j0) {
        // vertical
        for (int j1 = 0; j1 < N; j1++) {
            if (placed[i0][j1]) {return false;}
        }

        // horizon
        for (int i1 = 0; i1 < N; i1++) {
            if (placed[i1][j0]) {return false;}
        }

        // 대각선 조건
        for (int i1 = 0; i1 < i0; i1++) {
            int diffI = i0-i1;
            int newI = i0 - diffI;
            if (newI > 0) {
                int [] jArray = new int[]{j0 - diffI, j0 + diffI};
                for (int newJ : jArray) {
                    if (newJ < N) {
                        if (placed[newI][newJ]) {return false;}
                    }
                }
            }
        }
        return true;
    }
}