★ [백준][Java] 9663번 N-Queen (백트래킹, 브루트 포스)

시간 단축 가능함

밑에 2번째 코드의 Line:18 부분에서 시간이 많이 소요되는 것으로 보임..

(Line:18에서 이미 퀸을 놓은 좌표의 [같은 열, 슬래시, 백슬래시]에 속한 부분인지

첫번째부터 계속 탐색하고 있고 거리의 절대값도 매번 구해서 시간이 오래 걸리는 것 같음)

열에 속한다 또는 대각선(슬래시, 백슬래시에 속한다)를 boolean으로 체크해줘야함

규칙이 있었음

(솔직히 코딩테스트 같은 곳에서 풀라고 하면 첫번째 방법으로는 절대 못풀듯..

2번째 방식이 n_queen 이해하는데 입문하기도 쉽고 짜기도 편함 근데 시간은 2배 더 걸림)

 

 

참고 : https://herong.tistory.com/entry/BOJ-9663-N-Queen-Java

참고 링크 2번째 코드의

column, slash, backslash를 true하고 false하는 부분을 통해

무의미한 계산들을 줄일 수 있는 것 같음 

규칙을 찾을 수 있음 그게 이거임 규칙을 찾아야함 규칙

 

col[c] = slash[r + c] = backslash[r - c + N - 1] = true;

solve(r + 1);

col[c] = slash[r + c] = backslash[r - c + N - 1] = false;

 

여기서 진짜 헷갈리는 부분이 backslash slash였음..

column은 당연히 겹치니까 넘어가고

r+c만 true해주면 그거에 해당하는 slash부분이 전부 true된다고 보면됨

backslash도 마찬가지임

 

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static int N;
    static int res;
    static boolean[] isYused;
    static boolean[] slash;
    static boolean[] backSlash;
    
    private static void N_Queen(int X) {
        if(X>N) {
            /*for (int i : Y) {
                System.out.print(i+" ");
            }
            System.out.println();*/
            res++;
            return ;
        }
        
        
        for(int tempY=1; tempY<=N; tempY++) {
            if( !(isYused[tempY] || slash[tempY+X] || backSlash[N-(tempY-X)])){
                isYused[tempY] = slash[tempY+X] = backSlash[N-(tempY-X)] = true;
                N_Queen(X+1);
                isYused[tempY] = slash[tempY+X] = backSlash[N-(tempY-X)] = false;
            }
        }
        
    }
 
    public static void main(String[] args) throws IOException{
        N = stoi(br.readLine());
        res = 0;
        
        isYused = new boolean[N+1];
        slash = new boolean[2*N+1];
        backSlash = new boolean[2*N+1];
        N_Queen(1);
        
        System.out.println(res);
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
    
    
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
    
    
}

 

 

 

 

 

 

 

 

 

DFS로 푸니까 안풀림 이상하게 풀었음.. (DFS로 될리 없음)

 

2차원 배열을 이용하여 좌표를 만들 필요 없이

1차원 배열로 해결이 가능함

index가 x좌표고, 그 index의 원소값을 y좌표로 해서 안겹치는 모든 경우의 수를 생각하면 됨

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static int N;
    static int res;
    static int[] Y;
    
    private static void N_Queen(int X) {
        for(int preX=1; preX<X; preX++) {
            if(Y[preX]==Y[X] || X-preX == Math.abs(Y[X]-Y[preX]))
                return;
        }
        
        if(X==N) {
            /*for (int i : Y) {
                System.out.print(i+" ");
            }
            System.out.println();*/
            res++;
            return ;
        }
        
        for(int tempY=1; tempY<=N; tempY++) {
            Y[X+1] = tempY;
            N_Queen(X+1);
        }
        
    }
 
    public static void main(String[] args) throws IOException{
        N = stoi(br.readLine());
        res = 0;
        Y = new int[N+1];
        
        for(int fixY=1; fixY<=N; fixY++) {
            Y[1] = fixY;
            N_Queen(1);
        }
        System.out.println(res);
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
    
    
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
    
    
}