[백준 9663] N-Queen

 

N*N의 체스판에 N개의 퀸을 놓는 경우를 모두 체크해야 한다.

N개의 퀸을 모두 움직여봐야 하므로 백트래킹을 사용한다.

 

백트래킹은 설명이 좀 난해하여 로직을 서술하겠다.

 

퀸은 가로, 세로, 대각선으로 움직이는 말이라는 것을 사전에 알아야 한다.

 

코드 1

public class Main {
    
    static int n;
    static int a[][];
    static int cnt = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        a = new int[n+1][n+1];
        
        for(int i=1; i<=n; i++) {
            a[1][i] = 1;
            dfs(1, i);
            a[1][i] = 0;
        }
        
        System.out.println(cnt);
    }
    
    public static void dfs(int r, int c) {
        if(r == n) {
            cnt++;
            return;
        }
        
        for(int i=1; i<=n; i++) {
            if(setQueen(r+1, i)) {
                a[r+1][i] = 1;
                dfs(r+1, i);
                a[r+1][i] = 0;
            }
        }
    }
    
    public static boolean setQueen(int r, int c) {
        for(int i=1; i<r; i++) {
            for(int j=1; j<=n; j++) {
                if(a[i][j] == 1 && j == c)
                    return false;
                if(a[i][j] == 1 && Math.abs(i - r) == Math.abs(j - c))
                    return false;
            }
        }
        return true;
    }
}

맨 처음 사용한 로직이다.

말을 놓으면 1 놓지 않으면 0으로 구분한다.

2차원 배열이라서 퀸을 놓을 수 있는지 여부를 확인할때마다 2중루프를 돌게된다.

문제에서 요구하는 10초 이내에 들지 못해 1차원 배열로 바꾸었다.

 

 

코드 2

public class Main {
    
    static int n;
    static int a[];
    static int cnt = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        a = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            a[1] = i;
            dfs(1);
        }
        
        System.out.println(cnt);
    }
    
    public static void dfs(int r) {
        if(r == n) {
            cnt++;
            return;
        }
        
        for(int i=1; i<=n; i++) {
            a[r+1] = i;
            if(setQueen(r+1))
                dfs(r+1);
        }
    }
    
    public static boolean setQueen(int r) {
        for(int i=1; i<r; i++) {
            if(a[i] == a[r])
                return false;
            if(Math.abs(a[i] - a[r]) == Math.abs(i - r))
                return false;
        }
        return true;
    }
}

배열의 인덱스는 행, 배열의 값은 열로 사용했다.

배열의 값이 1, 0 혹은 true, false 등으로 말을 놓았는지의 여부를 확인하는게 아니라

몇번째 열에 두었는지 확인하기 때문에 백트래킹 이후 배열의 값을 다시 초기화해줄 필요가 없었다.