백준 9663번 : N-Queen [자바]

 

 

 

🧫 문제 분석

✔️ 출처

N-Queen 골드 4

 

📖 문제

 

많은 깨달음을 준 문제다.

 

퀸의 특성상 상하좌우대각을 원하는 만큼 이동이 가능하기에 

그에 따른 검증을 해야한다.

 

처음에는 이중 배열로 만들어서 각 퀸의 위치를 리스트에 저장하고 

리스트를 순회하면서 검증하고 놨는데 시간복잡도가 너무 크게 나와서 O((N^2)^N)

 

힌트를 보고 풀었다. 

 

퀸 특성상 n개의 체스판에서는 각 행에 하나씩 둬야 n개의 퀸을 둘 수 있다.

때문에 퀸을 두고 다음 행을 탐색한 후 돌아온 다음 다시 퀸을 지울 필요없이 덮어씌우면된다. (백트래킹에서)

 

 

나의 잘못된 생각은

검증시 0~n 행까지 전부 다 해서 쓸모없는 연산이 늘고, 잘못된 검증이 되어 값이 증가한 것이다. 

 

말했듯이 n개의 퀸을 놓을려면 0행부터 순서대로 n행까지 하나씩 놓아야하기때문에 

이전 행까지만 탐색하여 검증하면 된다. 

 

 

---

🔅 문제 풀이

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

public class Main {
    // NXN 체스판 위 N개를 놓는 방법 (서로 공격 X)
    // 행, 열, 대각 체크
    static int[] map;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        map = new int[n];
        dfs(n, 0);

        System.out.println(answer);
    }


    private static void dfs(int n, int row) {
        if (n == row) {
            answer++;
            return;
        }

        // 열
        for (int i = 0; i < n; i++) {
            // 이전 퀸들과 공격하는 위치에 있는지 확인
            if (available(row, i)) {
                map[row] = i;
                dfs(n, row + 1);
            }
        }
    }

    // 새로운 퀸을 놓을 수 있는지 검증
    private static boolean available(int y, int x) {
        // 각 행을 돌면서 체크
        for (int j = 0; j < y; j++) {
            // x축이 같거나 ,     x증가량 과 y증가량이 같다면 (이는 대각선을 의미)
            if (map[j] == x || Math.abs(j - y) == Math.abs(map[j] - x)) {
                return false;
            }
        }
        return true;
    }
}

 

 

✖️ 틀린 문제풀이

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

public class Main {
    // NXN 체스판 위 N개를 놓는 방법 (서로 공격 X)
    // 행, 열, 대각 체크
    static int[] map;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        map = new int[n];

        Arrays.fill(map, -1);
        dfs(n, 0);

        System.out.println(answer);
    }


    private static void dfs(int n, int cnt) {
        if (n == cnt) {
            System.out.println(Arrays.toString(map));
            answer++;
            return;
        }

        // 행
        for (int i = 0; i < n; i++) {
            if (map[i] != -1) continue;

            // 열
            for (int j = 0; j < n; j++) {
                // 이전 퀸들과 공격하는 위치에 있는지 확인
                if (cnt == 0 || available(n, i, j)) {
                    map[i] = j;
                    dfs(n, cnt + 1);
                    map[i] = -1;
                }
            }
        }
    }

    // 새로운 퀸을 놓을 수 있는지 검증
    private static boolean available(int n, int y, int x) {
        // 각 행을 돌면서 체크
        for (int k = 0; k < n; k++) {
            // x축이 같거나 ,     x증가량 과 y증가량이 같다면 (이는 대각선을 의미)
            if (map[k] == x || Math.abs(k - y) == Math.abs(map[k] - x)) {
                return false;
            }
        }
        return true;
    }
}

❗ 오답노트 / 필요한 지식

1.  생각날때마다 자주 풀어보자