[PS] BOJ9663 N-Queen ( BackTracking ) with JAVA

9663번: N-Queen

 

◎ 문제풀이

 

 

 

 

 

NxN의 체스판에 서로를 잡지 않을 위치에 N개의 퀸을 배치할 수 있는 경우의 수를 구하는 문제이다. 

 

퀸은 행, 열, 대각선 방향으로 이동한다. 

그러므로 행을 기준으로 하나의 행에는 하나의 퀸만 위치할 수 있다. 

 

 

 

( ROW1, COL1 )에 퀸이 위치한다면 ROW2에는 COL3, COL4, COL5에 퀸이 위치할 수 있다. 

 

모든 경우의 수를 완전탐색하는 방법에는 대표적으로 반복문과 재귀호출이 있다. 재귀호출의 장점은 메소드가 반복 호출되면서 이전의 데이터를 간직한다는 점이다. 그러므로 ROW1이 ROW2에 영향을 끼치고 ROW1,2가 ROW3에 영향을 끼치는 경우의 완전탐색은 재귀호출을 사용하는 것이 좋다. 재귀호출을 사용하는 대표적인 알고리즘이 DFS이다.

 

DFS를 하면서 완전탐색을 하되, 이전 Queen이 잡을 수 있는 위치는 탐색하지 않는 BackTracking을 해야한다.  행 하나에 하나의 퀸만 놓을 수 있으니 DFS의 호출 단위는 행(ROW)으로 한다. 그리고 퀸이 놓을 수 있는 열(COL)의 자리를 완전탐색하되, 이전 행의 퀸이 잡을 수 있는 열은 탐색하지 않는다. 

 

그럼 백트래킹의 조건을 따져보자.

 

퀸은 행, 열, 대각선으로 이동하므로 행, 열, 대각선의 위치에 다른 퀸이 놓이면 안 된다.

 

1) 행 : DFS는 행을 기준으로 호출되므로 신경 쓰지 않아도 된다. 

 

2) 열 : 이전에 놓인 퀸과 열(COL)이 일치하면 안된다.

 

3) 대각선 : 대각선으로 한칸을 이동하면,  행과 열은 동시에 +1,+1, 하거나 -1,-1 하거나 +1,-1 하거나 -1,+1로 이동한다. 한마디로 행과 열이 절대값 1만큼 동시에 이동한다는 의미이다. 그러므로 ( r1, c1 ) 과 ( r2, c2 )가 같은 대각선상에 있다면

 

| r2 - r1 | == | c2 - c1 | 이 성립한다. 

 

정리하면, 현재 위치에 퀸을 놓으려면 이전에 놓았던 퀸과 열이 일치하면 안되고 각 행과 열의 차이의 절대값도 같으면 안 된다는 의미이다. 이 조건을 만족하면 현재 위치에 퀸을 놓을 수 있다.  그러므로 재귀호출을 진행하면서, 퀸의 위치를 저장하는 테이블을 만들어 백트래킹 조건을 따져보아야 한다.

 

나는 | r2 - r1 | == | c2 - c1 | 이 조건을 도출하지 못하여, 체스판을 이차원 배열로 만들고 재귀호출을 진행할 때마다 방문가능 여부를 체크하는 방식으로 문제를 풀었는데, 메모리 초과가 발생했다. 모든 경우를 따져보아야 하므로 경우를 따질 때마다 이차원 배열을 새로 만들어서 그랬다.  | r2 - r1 | == | c2 - c1 |  조건은 간단하면서도 발상이 어려운거 같다. 

 

◎ 코드

 

- 정답 코드

//BOJ9663 N-Queen
public class Bt7 {

    static int n;
    static int ans;
    static int[] queens;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        queens = new int[n]; // 퀸의 위치를 담은 테이블 [ 인덱스 : ROW, 값 : COL ]

        dfs(0); // DFS 탐색

        System.out.println(ans);

    }

    public static void dfs(int row){ // 행을 기준으로 탐색
        if(row == n){
            ans+=1;
            return;
        }

        for(int col=0;col<n;col++){ // 열을 기준으로 탐색
            if(isValid(row,col)){
                queens[row] = col;
                dfs(row+1);
            }
        }
    }

    public static boolean isValid(int row, int col){
        for(int r =0;r<row;r++){ // 현재 놓여진 퀸 완전탐색
            if(queens[r] == col) return false; // 열에 겹치는 경우
            if(row-r == Math.abs(queens[r]-col)) return false; // 대각선에 겹치는 경우
        }
        return true;
    }
}

 

- 내가 풀이한 코드 ( 메모리 초과 발생 )

package org.example.backtracking;


import java.util.Scanner;

//BOJ9663 N-Queen ( 메모리 초과 버전 )
public class Bt6 {

    static int n;
    static int ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0,new boolean[n][n]);

        System.out.println(ans);
    }

    public static void dfs(int depth, boolean[][] board){
        if(depth == n) {
            ans += 1;
            return;
        }

        for(int i=0;i<n;i++){
            if(board[depth][i]) continue;

            boolean[][] tmpBoard = copy(board);
            updateChessBoard(i,depth,tmpBoard);
            dfs(depth+1,tmpBoard);
        }
    }

    public static boolean[][] copy(boolean[][] original){
        boolean[][] copy = new boolean[n][n];
        for(int i=0;i<n;i++){
            copy[i] = original[i].clone();
        }
        return copy;
    }

    public static void updateChessBoard(int x, int y, boolean[][] board ){

        int[] dx = { 0, 1, 0, -1, 1, -1, 1, -1 };
        int[] dy = { 1, 0, -1, 0,  1, -1, -1, 1 };

        for(int i=0;i<8;i++){
            update(x,y,dx[i],dy[i],board);
        }
    }

    public static void update(int x, int y, int dx, int dy,boolean[][] board){

        while(x<n&&y<n&&x>=0&&y>=0){
            board[y][x] = true;
            x += dx;
            y += dy;
        }

    }
}