[JAVA] 백준 #9663 N-Queen | Back Tracking | 시간 복잡도 최적화

[JAVA] 백준 #9663 N-Queen

 

🔒 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

---

🔎  풀이

처음에 풀 때는 배열 완전 탐색을 생각했다. 그래서 체스 보드판은 이중 배열로 선언하고 board[N][N], 이중 배열 보드를 Back tracking을 돌면서 퀸을 N개 놓고, 그 조합이 정답인지 아닌지 확인하는 방식으로 코드를 구성했다.

 

🔹최적화 전

    static void placeTheQueen( int count, int startI, int startJ ){
        if( count == N ){
            checkIfCanAttack();
            return;
        }

        for( int i = startI; i < N; i++ ){
            for( int j = startJ; j < N; j++ ){
                if( board[i][j] == 0 ) {
                    board[i][j] = 1;
                    queens.offer(new int[]{i,j});
                    placeTheQueen(count + 1, i, j+1);
                    board[i][j] = 0;
                }

            }
        }
    }

 

그런데 만약 열을 기준으로 생각한다면 어차피 퀸이 서로를 공격하지 않으려면 한 열에 퀸을 두었을 때 그 열은 이제 더 이상 퀸을 둘 수 없으므로 다음 열로 무조건 이동해야 한다. 그렇다면 여기서 우리는 인덱스가 하나만 필요하다는 것을 알 수 있다. 위의 코드처럼 이중 for문으로 돌릴 필요가 없는 것이다.

 

더 나아가서 이를 보드 판에 적용하면 board를 단일 배열로 두고 i를 열, board[i]는 행으로 둬서 시간 복잡도를 훨씬 줄일 수 있다. 

 

🔹최적화 후

    public static void placeTheQueen( int col){
        if( col == N ) {
            answer ++;
            return;
        }

        for( int row = 0; row < N; row++ ){
            if(checkTheQueen( col, row )){
                board[col] = row;
                placeTheQueen(col + 1 );
            }
        }
    }

 

백트래킹을 할 때 해당 자리에 말을 둬도 되는지 안되는지 여부는 checkTheQueen() 메서드로 확인할 수 있다. 이미 존재하는 퀸들과 현재 두려는 자리를 비교하는 과정을 구현했는데 현재 두려는 말과 퀸의 말이 같은 줄에 있을 경우(board [i] == row ), 그리고 퀸의 대각선에 위치하고 있는 경우 (Math.abs( board[i] - row ) == Math.abs( i - col) )는 false를 리턴해 퀸을 두지 않고, 그렇지 않은 경우에는 퀸을 둔다. 

 

🔹 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[] board;
    static int N;
    static int answer = 0;

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

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        board = new int[N];

        placeTheQueen(0);

        System.out.println(answer);
    }

    public static void placeTheQueen( int col){
        if( col == N ) {
            answer ++;
            return;
        }

        for( int row = 0; row < N; row++ ){
            if(checkTheQueen( col, row )){
                board[col] = row;
                placeTheQueen(col + 1 );
            }
        }
    }

    public static boolean checkTheQueen(int col, int row){
        for( int i = 0; i < col; i++ ){
            if( board[i] == row || ( Math.abs( board[i] - row ) == Math.abs( i - col) )){
                return false;
            }
        }
        return true;
    }

}