[알고리즘] 9663. N-Queen

0. 문제

 

9663번: N-Queen

 

---

1. 문제 이해

 

1. 백트래킹

 

---

2. 시간 초과

 

n이 14일 때 10초 이내로 통과해야 함.

 

가. 시간 초과

import java.util.Scanner;

public class BOJ9663 {

    static int[] map;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 체스판을 1차원 배열로 표현
        // y행 x열 -> map[y*n + x]
        map = new int[n*n]; 

        int ret = solve(n, 0, 0, -1);
        System.out.println(ret);
        sc.close();
    }

    private static int solve(int n, int depth, int start, int cur) {
        //가지치기
        if(cur >0 && !check(n, cur)) { // 새로 추가한 퀸에 대하여 검사
            return 0;
        }

        //기저조건
        if(depth==n) {
            return 1;
        }

        //중복없는 조합 생성
        int sum = 0;
        int end = (n*n);
        for(int i=start; i<end; i++) {
            map[i] = 1; // 퀸 추가
            sum += solve(n, depth+1, i+(n-(i%n)), i); // 같은 행은 넘기고
            map[i] = 0; // 원복
        }

        return sum; 
    }

    // 서로 공격하면 false
    private static boolean check(int n, int pos) {
        // y행 x열 -> map[y*n + x]
        //가로
        for(int y=pos/n, x=0; x<n; x++) {
            int idx = (y*n)+x;
            if(idx == pos) continue;
            if(map[idx]==1) {
                // System.out.println(idx + " check1");
                return false;
            }
        }
        //세로
        for(int x=pos%n, y=0; y<n; y++) {
            int idx = (y*n)+x;
            if(idx == pos) continue;
            if(map[idx]==1) {
                // System.out.println(idx + " check2");
                return false;
            }
        }
        //대각
        int y=pos/n;
        int x=pos%n;
        for(int i=0; i<n; i++) { // 왼쪽 위 -> 오른쪽 아래
            int ny = y - x + i;
            int nx = i;
            if(ny < 0 || ny >= n) continue;
            int idx = ny*n + nx;
            if(idx == pos) continue;
            if(map[idx]==1) {
                // System.out.println(idx + " check3");
                return false;
            }
        }
        for(int i=0; i<n; i++) { // 왼쪽 아래 -> 오른쪽 위
            int ny = y + x - i;
            int nx = i;
            if(ny < 0 || ny >= n) continue;
            int idx = ny*n + nx;
            if(idx == pos) continue;
            if(map[idx]==1) {
                // System.out.println(idx + " check4");
                return false;
            }
        }
        return true;
    }

}

 

---

나. 방문체크 사용하기

import java.util.Scanner;

public class BOJ9663 {

    static int[] visited;
    public static void main(String[] args) {
        //long time = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 체스판을 1차원 배열로 표현
        // y행 x열 -> map[y*n + x]
        visited = new int[n*n]; 

        int ret = solve(n, 0, 0);
        System.out.println(ret);
        //long secDiff = System.currentTimeMillis() - time;
        //System.out.println(secDiff);
        sc.close();
    }

    private static int solve(int n, int depth, int start) {
        //기저조건
        if(depth==n) {
            return 1;
        }

        //중복없는 조합 생성
        int sum = 0;
        int end = (n*n);
        for(int i=start; i<end; i++) {
            if(visited[i]>0)continue;
            go(n, i, 1);
            sum += solve(n, depth+1, i+1);
            go(n, i, -1);
        }

        return sum; 
    }

    //더 이상 사용할 수 없는 위치를 방문 체크 혹은 체크 해제
    private static void go(int n, int pos, int num){
        // y행 x열 -> map[y*n + x]
        visited[pos]+=num;
        //가로
        for(int y=pos/n, x=0; x<n; x++) {
            int idx = (y*n)+x;
            if(idx == pos) continue;
            visited[idx] += num;
        }
        //세로
        for(int x=pos%n, y=0; y<n; y++) {
            int idx = (y*n)+x;
            if(idx == pos) continue;
            visited[idx] += num;
        }
        //대각
        int y=pos/n;
        int x=pos%n;
        for(int i=0; i<n; i++) { // 왼쪽 위 -> 오른쪽 아래
            int ny = y - x + i;
            int nx = i;
            if(ny < 0 || ny >= n) continue;
            int idx = ny*n + nx;
            if(idx == pos) continue;
            visited[idx] += num;
        }
        for(int i=0; i<n; i++) { // 왼쪽 아래 -> 오른쪽 위
            int ny = y + x - i;
            int nx = i;
            if(ny < 0 || ny >= n) continue;
            int idx = ny*n + nx;
            if(idx == pos) continue;
            visited[idx] += num;
        }

    }

}

 

---

다. 정답

 

죽어도 못 푼다.

 

import java.util.Scanner;

public class Main {

    public static int[] arr;
    public static int N;
    public static int count = 0;

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        arr = new int[N];

        nQueen(0);
        System.out.println(count);

    }

    // depth 행 
    public static void nQueen(int depth) {
        if (depth == N) { // 조건을 만족하는 경우
            count++;
            return;
        }

        for (int i = 0; i < N; i++) {
            arr[depth] = i; // depth 행 i 열에
            if (Possibility(depth)) { // 놓을 수 있는 경우 재귀호출
                nQueen(depth + 1); // 다음 행
            }
        }

    }

    public static boolean Possibility(int col) {

        for (int i = 0; i < col; i++) {
            // 같은 열?
            // col 행의 열과 i 행의 열이 같다면 -> 같은 열에 위치
            if (arr[col] == arr[i]) {
                return false;
            } 

            //같은 대각선?
            //(열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다)
            else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
                return false;
            }
        }

        return true;
    }
}

 

• arr = new int[N]; : 한 행에 퀸은 한 개만 위치할 수 있기 때문에 int[N]으로도 충분히 체스판을 표현할 수 있다.
• if (arr[col] == arr[i]) { : 같은 열에 위치했는지 확인하는 방법.
• if(Math.abs(col - i) == Math.abs(arr[col] - arr[i])) { : 같은 대각선에 위치했는지 확인하는 방법.

 

익숙해지도록 노력하자.

 

---