백준 9663번: N-Queen (JAVA)

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

---

풀이

1. 내 풀이: 어제 하던 백트래킹(N과 M 1부터 12까지)과 비슷한 구조로 코드를 짜되, visited를 boolean이 아니라 int type으로 저장하여 하나의 퀸이 해당 칸에 영향을 미칠때마다 +1씩 해줬다. 그래야 퀸이 1개라도 있을 때 해당 칸에 배치하지 못한다는 점이 유지가 되더라.
2. N < 15라는 점에 착안, 위에서 구한 정답을 int[14] array에 저장하여 출력하는 풀이. O(1) 풀이이다ㅋㅋ
3. 백준 코드에서 본 다른 선생님분의 풀이: col, 대각선1, 대각선2에 퀸이 있는지를 boolean으로 저장한다. 아이디어가 뛰어나며 효율이 좋다.

 

코드

풀이 1

import java.util.Scanner;

public class Main {
    static int N, totalCnt;
    static int[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        visited = new int[N][N];
        dfs(0);
        System.out.println(totalCnt);
    }

    public static void dfs(int cnt) { 
        if (cnt == N) {
            totalCnt++;
            return;
        }

        for (int col = 0; col < N; col++) {
            if (visited[cnt][col] > 0) continue;
            visitedAdd(cnt, col, 1);
            dfs(cnt+1);
            visitedAdd(cnt, col, -1);
        }
    }

    public static void visitedAdd(int row, int col, int n) {
        for (int j = col; j<N; j++) {
            visited[row][j] += n;
        }
        for (int i = row + 1; i < N; i++) {
            visited[i][col] += n;
        }
        for (int i = 1; i < N - row && i < N - col; i++) {
            visited[row+i][col+i] += n;
        }
        for (int i = 1; row + i < N && col - i >= 0; i++) {
            visited[row+i][col-i] += n;
        }
    }
}

 

풀이 2 (=야매)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int[] answer = {0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596};
        Scanner sc = new Scanner(System.in);
        System.out.println(answer[sc.nextInt()]);
    }
}

 

풀이 3 

import java.io.*;

public class Main {
    static int N, ans;
    static boolean[] col, diagonal1, diagonal2;

    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];
        diagonal1 = new boolean[2*N+1];
        diagonal2 = new boolean[2*N+1];
        dfs(0);
        System.out.println(ans);
    }


    static void dfs(int r) {
        if (r >= N) {
            ans++;
            return;
        }

        for (int c = 0; c < N; c++) {
            if (col[c] || diagonal1[r+c] || diagonal2[N-1-c+r]) continue;
            col[c] = true;
            diagonal1[r+c] = true;
            diagonal2[N-1-c+r] = true;
            dfs(r+1);
            col[c] = false;
            diagonal1[r+c] = false;
            diagonal2[N-1-c+r] = false;
        }
    }
}

 

P.S.

풀이 2의 기적적으로 짧은 runtime에 낚인 사람들이 많다.

​