백준 - 9663 - N-Queen

 

www.acmicpc.net/problem/9663

9663번: N-Queen

import java.util.*;

/**
 * 백준 9663
 */
public class N_Queen {
    private static int M = -1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        M = N;
        sc.close();
        //nqeen(N);
        nqeen2(N,new ArrayList<>());
        System.out.println(count);
    }

	//시간복잡도의 성능이 더 좋은 버전
    private static Set<Integer> columnSet = new HashSet<>();
    private static Set<Integer> plusSet = new HashSet<>();
    private static Set<Integer> minusSet = new HashSet<>();
    private static int count = 0;
    private static void nqeen(int N) {
        //종료
        if(N == 0) {
            count++;
            return;
        }

        //프로세스
        for(int i=1; i<=M; i++) {
            int plus = i + N;
            int minus = i - N;
            if(!columnSet.contains(i) && !plusSet.contains(plus) && !minusSet.contains(minus)) {
                minusSet.add(minus);
                plusSet.add(plus);
                columnSet.add(i);
                nqeen(N-1);
                columnSet.remove(i);
                plusSet.remove(plus);
                minusSet.remove(minus);
            }
        }
    }

	//공간복잡도의 성능이 더 좋은 버전
    private static void nqeen2(int N, List<Integer> prefix) {
        //종료
        if(N == 0) {
            count++;
            //System.out.println(prefix);
            return;
        }

        //프로세스
        for(int i=1; i<=M; i++) {
            int plus = i + N;
            int minus = i - N;
            //유효성 검사
            boolean isAble = true;
            int row = M;
            for(int j=0; j<prefix.size(); j++) {
                int col = prefix.get(j);
                if(plus == row+col || minus == col-row || col == i) {
                    isAble = false;
                    break;
                }
                row--;
            }

            if(isAble) {
                prefix.add(i);
                nqeen2(N-1, prefix);
                prefix.remove(prefix.size()-1);
            }
        }
    }
}

 

문제해석

N*N 보드가 주어졌을때 N개의 퀸을 보드 위에 놓는 경우 중 서로 공격할 수 있는(같은 행, 같은 열, 같은 대각선에 일치) 경우를 제거한 모든 경우의 수를 출력하는 문제.

 

알고리즘

백트래킹, 순열

• 문제의 핵심은 만약 N이 4일 경우 처음에 퀸을 놓을 수 있는 경우는 16가지가 된다. 근데 생각해보면 퀸은 서로 같은 행에 놓을 수 없음으로 한 행만 따로 분리하여 생각하면 4가지로 줄일 수 있다.
• 이렇게 생각했을때 모든 조합에서 각 행에 퀸을 놓을 수 있는 위치만 생각해주면 된다.
• 퀸을 놓을 수 있는지 판단하는 시간복잡도는 O(N)이 걸린다. N개의 퀸의 위치와 현재 놓으려고 하는 퀸을 비교해서 같은 행, 같은 열, 같은 대각선에 위치하는지 검사해주면 되기 때문이다.
• 하지만 같은 행인 경우는 배제하고 진행하기 때문에 따로 검사하지 않아도 되고 대각선인 경우는 위치의 합과 차이가 같은 대각선이면 같은 성질을 이용하여 판단할 수 있다.
• 하지만 이 로직을 HashSet을 이용하면 O(1)로 줄일 수 있다. 하지만 백준에서는 메모리 초과에 걸리게 되므로 순회하여 O(N)의 시간복잡도를 가져가야한다.