[BOJ] 백준 9663 N-Queen

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

 Input 
8

 Output 

92

체스판에서 퀸(x, y)의 이동은 같은 행, 열 그리고 대각선 방향입니다.

두 좌표가 (x1,y1), (x2,y2)일 때, |x1- x2 | = | y1 - y2|이면 

좌표상 대각선상에 있다고 볼 수 있습니다.

ex) A=(1,1) / B=(5,5)가 존재하면, |5-1| = |5-1| 이므로 대각선상의 위치.

 

1행을 기준으로 퀸을 한개씩 놓아서 재귀 탐색처리.

1~N행까지 서로 공격하지 않게 퀸을 놓을 수 있는 모든 경우를 구합니다.

 

ex) 4 x 4 크기의 체스판

만약 1행에 두번째에 퀸을 두었다면 아래의 형태가 됩니다.

(특정 행에서는 여왕이 하나입니다.)

 

다른 풀이: [Jungol] 1889 N Queen

[Jungol] 정올 1889 N Queen

import java.util.Scanner;

public class Main {
    static int[] col;
    static int N;
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
        
        System.out.print("체스판의 크기 설정: ");
        N = Integer.parseInt(sc.next());
        
        col = new int[N+1];
        
        // 1 ~ (N-1)행까지 임의로 여왕말 위치를 설정하겠다.
        for(int i=1; i<N; i++) {
            System.out.print(i + "번째에서 몇 번째 열에 여왕을 놓으시겠습니까? ");
            // i번째 행의 몇 번째 열에 여왕말을 놓을지 설정한다.
            col[i] = Integer.parseInt(sc.next());    
        }
        
        
        // 마지막 행 N이 놓일 수 있는 위치를 확인해보자.
        System.out.println("==================================");
        System.out.println("마지막 행에서는 다음과 같은 위치에 놓을 수 있습니다.");
        for(int j=1; j<=N; j++) {
            col[N] = j;
            if(promising(N)) {
                System.out.println("[" + j + "] 번째 위치는 놓을 수 있습니다.");
            }
        }


    }
    
    private static boolean promising(int row) {
        // 1 ~ (row-1)행까지 위치한 여왕말이 공격할 수 있는 위치인지 확인
        for(int x=1; x < row; x++) {
            // 같은 열 혹은 대각선 위치에 있다면 False 반환
            if(col[x] == col[row] || Math.abs(row-x) == Math.abs(col[row]- col[x]))
                return false;
        }
        
        // 놓을 수 있는 위치이면 True 반환
        return true;
    }
}

---

import java.util.Scanner;

public class Main {
    
    static int[] col;
    static int N, answer;
    
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
        
        N = Integer.parseInt(sc.next());
        col = new int[N+1]; // 각 행에서 여왕이 위치한 열이 몇 번째인지 저장할 배열
        
        
        // 우선 첫번째 행에서 여왕들이 모든 열에 놓아보면서 탐색
        for(int j=1; j<=N; j++) {
            // 1번째 행에 j번째 열에 여왕
            col[1] = j;
            
            // 2번째 행에서는 여왕을 어떻게 놓을지 탐색하는 것 (재귀)
            DFS(2);
        }
        
        // 정답 출력
        System.out.println(answer);
    }
    
    private static void DFS(int row) {
        // 만약 N+1 수치에 도달했다면
        // N번째 행까지 1개씩 놓으면서 N개의 여왕을 놓는데 성공
        if(row > N) {
            answer++;
            return;
        }
        // row번째 행에 여왕이 놓일 수 있는 열 위치를 확인한다.
        for(int y=1; y<=N; y++) {
            col[row] = y;
            // 만약 지금까지 상태에서 여왕끼리 서로 공격할 수 없는 위치라면 계속해서 탐색하고
            // 그렇지 않으면 더 이상의 탐색은 의미 없다.(백트래킹)
            if(promising(row)) {
                // 다음 몇 번째 행을 살펴야 할지 인자로 전달한다.
                DFS(row+1);
            }
        }
        
    }

    private static boolean promising(int row) {
        // 1 ~ (row-1)행까지 위치한 여왕말이 공격할 수 있는 위치인지 확인
        for(int x=1; x < row; x++) {
            // 같은 열 혹은 대각선 위치에 있다면 False 반환
            if(col[x] == col[row] || Math.abs(row-x) == Math.abs(col[row]- col[x]))
                return false;
        }
        
        // 놓을 수 있는 위치이면 True 반환
        return true;
    }
}