[백준 JAVA] 9663번: N - Queen

https://www.acmicpc.net/problem/9663

 

대표적인 백트래킹 문제

 

예전에 풀어봤다고 생각했는데 제출은 안한거 같다.

 

1. 모든 경우의 수를 재귀로 들어가는 것이 아닌 백트래킹을 통해 제외되는 경우의 수는 탐색하면 안된다.

 

2. 위치를 2차원 배열로 저장해서 방문처리를 사실 같은 열에는 하나의 퀸밬에 들어가지 못하므로 1차원 int 배열로도 가능하다

 

예를들어 (1, 2), (2, 4) 에 퀸이 놓여있는 상황에서

 

평소처럼 이차원 배열로 표시하면 map[1][2] = true, map[2][4] = true 로 표시해야하지만

 

1차원 int 배열로는 map[1] = 2, map[2] = 4 이런식으로 표현이 가능하다.

 

3. 대각선을 체크하기 위해 기울기를 사용한다. r1 - r2 = c1 - c2 라면 기울기가 같으므로 같은 대각선에 놓여있는 상황이다.

 

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

public class Main {
    public static int N, ans = 0;
    public static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        dfs(0);

        System.out.println(ans);
    }
    public static void dfs(int depth){
        if(depth == N) {
            ans++;
            return;
        }
        for(int i = 0; i < N; i++){
            arr[depth] = i;
            if (valid(depth)){
                dfs(depth + 1);
            }
        }
    }
    public static boolean valid(int r){
        for(int i = 0; i < r; i++){
            if(arr[i] == arr[r]) return false;
            if(Math.abs(i - r) == Math.abs(arr[i] - arr[r])) return false;
        }
        return true;
    }
}

 

이런식으로 valid 함수를 만들어서 가능한 경우에만 재귀할 수 있도록 만들었는데 GPT 를 통해 리팩토링 했더니

 

시간 복잡도는 O(N!) 이고 valid가 N정도 걸리므로 O(N! * N) 걸린다. 

 

이때 valid 하는것을 O(1)만에 할 수 있다해서 코드를 좀 수정해보았다.

 

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

public class Main {
    public static int N, ans = 0;
    public static int[] arr;
    public static boolean[] col, d1, d2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        col = new boolean[N];
        d1 = new boolean[2 * N - 1];
        d2 = new boolean[2 * N - 1];

        dfs(0);

        System.out.println(ans);
    }
    public static void dfs(int r){
        if(r == N) {
            ans++;
            return;
        }
        for(int c = 0; c < N; c++){
            int k1 = r - c + (N - 1), k2 = r + c;
            if (col[c] || d1[k1] || d2[k2]) continue;
            arr[r] = c;
            col[c] = d1[k1] = d2[k2] = true;
            dfs(r + 1);
            col[c] = d1[k1] = d2[k2] = false;
        }
    }
}

 

이런식으로 열, +대각선, -대각선 방문처리 + 원상복구로 한다면 방문확인을 O(1)만에 할 수 있게 되므로 시간이 많이 줄어드는것을 확인 할 수 있었다.

 

위에가 GPT답안, 밑에가 내가 푼 답안이다.

 

솔직히 쉽게 풀진 못했다. 백트래킹에 대한 이해와 대각선을 확인하는것을 자주 기억해야될듯하다.