백준 9663번 N-Queen JAVA

링크텍스트

설명

유명한 백트래킹 문제인 N-Queen 문제다. 예전부터 한 번 풀어보려고 했는데 오늘에서야 도전해봤다. 처음에는 2차원 배열과 2차원 체크 배열을 사용해서 풀었지만, n이 15일 경우 실행 시간이 너무 오래 걸렸다.
그래서 시간을 줄이기 위해 열과 대각선을 나타내는 1차원 배열을 만들어 최적화했다.

대각선 판별은 다음과 같이 했다:
↗, ↙ 방향 대각선은 row + col 값이 같고
↖, ↘ 방향 대각선은 row - col 값이 같다.
다만 row - col은 음수가 나올 수 있어서, 배열 인덱스로 사용하려면 row - col + (n - 1)로 보정해주었다.

시간복잡도: O(N!), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.util.*;
import java.io.*;

class Main {
        static int n;
        static boolean [] col;
        static boolean [] diag1;
        static boolean [] diag2;
        static int count = 0;

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

        n = Integer.parseInt(br.readLine());

        col = new boolean[n];
        diag1 = new boolean[2*n-1];
        diag2 = new boolean[2*n-1];

        backtracking(0);

        System.out.println(count);
    }

    public static void backtracking(int depth){
        if(depth==n){ //depth = 행번호
            count++;
            return;
        }

        for(int j=0;j<n;j++){
            if(!col[j] && !diag1[depth+j] && !diag2[depth-j+n-1]){
                col[j] = diag1[depth+j] = diag2[depth-j+n-1] = true;
                backtracking(depth+1);
                col[j] = diag1[depth+j] = diag2[depth-j+n-1] = false;
            }
        }
    }
}

// 디버깅용
public static void backtracking(int depth){
        if(depth==n){
            count++;
            System.out.println("해답 찾음! count = " + count);
            return;
        }
    
        for(int j=0;j<n;j++){
            if(!col[j] && !diag1[depth+j] && !diag2[depth-j+n-1]){
                System.out.println("depth: " + depth + ", 열: " + j + " → 퀸 놓음");
    
                col[j] = diag1[depth+j] = diag2[depth-j+n-1] = true;
                backtracking(depth+1);
                col[j] = diag1[depth+j] = diag2[depth-j+n-1] = false;
    
                System.out.println("depth: " + depth + ", 열: " + j + " → 퀸 뺌 (백트래킹)");
            }
        }
 //

시간초과 코드

import java.util.*;
import java.io.*;

class Main {
        static int n;
        static int [][] arr;
        static boolean [][] check;
        static int count = 0;

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

        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        check = new boolean[n][n];

        backtracking(0);

        System.out.println(count);

    }

    public static void backtracking(int depth){
        if(depth==n){
            count++;
            return;
        }

        for(int j=0;j<n;j++){
            if(canCheck(depth,j)){
                check[depth][j] = true;
                backtracking(depth+1);
                check[depth][j] = false;
            }
        }
    }

    public static boolean canCheck(int x,int y){

        for(int i=0;i<x;i++){
            for(int j=0;j<n;j++){
                if(check[x][y]){
                if(j==y) return false;
                if(i-j == x-y) return false;
                if(i+j == x+y) return false;
                }
            }
        }


        return true;
    }
}