[BOJ/JAVA] 백준 9663번 N-Queen ( 백트래킹 )

 

✔ 문제

난이도 : 골드4 🥇

9663번: N-Queen

 

 

✔ 문제 풀이

N x N의 체스판  위에 N개의 퀸을 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제입니다.

Queen 공격범위

 

🤔 처음 접근

처음 접근할 때에는 첫번째 퀸을 두고 그 퀸의 공격범위를 모두 체크(방문처리)한 후 공격범위가 아닌 부분 부터 두번째 퀸을 두고 공격범위를 체크하며 나아가다 퀸 N개 즉 깊이(depth)가 N이 되었을때 리턴하여 백트래킹을 수행하려고 했습니다.

 

하지만 공격범위를 모두 체크하는 과정에서 이중 for문을 사용하였고 재귀호출이 끝난 후 다시 체크한 공격범위를 해제해  줘야 하기 때문에 이 과정에서 한번 더 이중 for문이 사용되었습니다, 결과적으로 많은 시간이 걸릴 수 밖에 없었습니다.

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

public class Main{

    static int n, cnt;
    static int[][] board;
    static int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
    static int[] dy = {0, 1, 0, -1, 1, -1, 1, -1};
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));      
        n = Integer.parseInt(br.readLine());

        board = new int[n][n];
        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                board[i][j] = -1;
            }
        }

        dfs(0);
        System.out.println(cnt);
	}
    
    static void dfs(int depth){
        if( depth == n){
            cnt++;
            return;
        }
        for( int i = 0; i<n; i++){
                if( board[depth][i] < 0){
                    check(depth, i, 1);
                    dfs(depth + 1);
                    check(depth, i, -1);
                }
        }
    }
    
    static void check(int y, int x, int chk){
   		board[y][x] += chk;
        for( int k = 1; k<n; k++){
            for( int l = 0; l<8; l++){
                int nx = x + ( k * dx[l] );
                int ny = y + ( k * dy[l] );
                if( nx < 0 || ny < 0 || nx >= n || ny >= n ) continue;
                board[ny][nx] += chk;
            }
        }
        
    }
}

 

 

💡 다른 풀이

다른 풀이를 참고하여 풀어보았습니다.

사실 이해하는데 꽤 많은 시간이 걸렸습니다😭

백트래킹 하는 과정이 익숙하지 않기도 하고 일차원 배열을 이차원 배열처럼 표현하여 머릿속으로 잘 그려지지 않았던 것 같습니다.

 

처음 풀이와는 다르게 퀸이 체스판 위에 있을때 모든 범위를 체크하지 않고, 다음 퀸의 범위에서 이전 퀸들이 있는지를 체크하는 식으로 풀어냈습니다.

또한 1차원 배열을 사용하여 2차원 배열처럼 board의 index를 행(row) 으로 index의 해당하는 값을 열(column)로 표현하여 메모리를 줄일 수 있습니다.

 

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

public class Main{
    static int n, cnt;
    static int[] board;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        board = new int[n];
        
        dfs(0);
        System.out.println(cnt);
	}
    static void dfs( int depth ){
        if( depth == n ){
            cnt++;
            return;
        }

        for( int i = 0; i<n; i++){
            board[depth] = i;
            if( isOk(depth) ){
                dfs( depth + 1);
            }
        }
    }

    static boolean isOk(int depth){
        for( int i = 0; i<depth; i++){
            if( board[i] == board[depth]){
                return false;
            } else if (Math.abs(depth - i) == Math.abs(board[depth] - board[i])) {
                return false;
            }
        }
        return true;
    }
}

 

 

🔎 if ( board[i] == board[depth] )

체스판에서 이전에 놓여진 퀸과 같은 열(column)에 위치하는지 여부를 묻는 조건 입니다.

 

 

🔎 else if ( Math.abs(depth - i) == Math.abs( board[depth] - board[i] ) )

체스판에서 대각선에 다른 퀸이 있는지 여부를 묻는 조건 입니다.

대각선임을 알 수 있는 방법은 같은 축끼리 뺀 수가 같다면 대각선상에 있다고 할 수 있습니다. ( 표 참고 )

 

for문의 범위를 depth까지 설정했습니다 즉 현재 퀸 이전의 놓인 퀸들의 위치는 i 를 통해서 알 수 있습니다.

Math.abs( depth - i ) : 현재 퀸의 y( depth ) - 이전 퀸의 y( i ) 라고 할 수 있습니다.

Math.abs( board[depth] - board[i] ) : 현재 퀸의 x - 이전 퀸의 x 라고 할 수 있습니다.