[백준/Java] 9663 N-Queen

조건

1. N * N 사이즈의 체스판에 퀸 N개를 서로 공격당하지 않는 위치에 놓아라

2. 퀸은 같은 행, 열 및 대각선으로 이동 가능하다

핵심

체스판 문제의 핵심은 체스판의 특징을 아는 것이다.

간단하게 패드로 그린 N = 6인 체스판이다.

여기서 초록색원형이 퀸이라고 할 때 서로 공격이 가능하다. 이것을 어떻게 코드에서 구현을 하느냐는 바로 체스판의 행과 열을 이용하여 찾을 것이다.

퀸의 위치에서 왼쪽 대각선 위로 오른쪽 대각선 아래로의 값들은 행에서 열을 빼면 값들이 다 같은 값이 나온다. (왼쪽 대각선 아래로 오른쪽 대각선 위로는 행 + 열 이다)

즉 현재 퀸(2,1)과 퀸(3,2)로 예를 들어보면 2-1 = 1이 나오고 , 3-2 = 1이 나온다 이렇게 행과 열을 이용하여 True, False를 찾아 공격이 가능한 Brute force 알고리즘에서 중간에 Boolean값을 통해 True가 나오면 for문을 중단 시켜 시간복잡도를 줄일 수 있다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    
    public static int[] arr;  // 열 배열 
    public static int N;    // 놓을 퀸의 숫자
    public static int ans = 0; // 놓을 수  있는 퀸 자리 수
    
    
    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+1];                   // 퀸의 숫자에 +1을 해주는 이유는 N개의 퀸을 다 놓아줘야하는데 같은 행에 퀸을 놓을 수 없으니 갯수 만큼의 행이 필요로함
  
        dfs(1); // 배열 1행 부터 차례대로 퀸을 놓으면서 함수의 시작 
        System.out.println(ans); // 전체 ans의 수  즉, 놓을 수 있는 수를 출력
    }

 static boolean attackable(int r1, int c1, int r2, int c2) {
        if (c1 == c2) return true; // 같은 행에 있으면 공격이 가능하기에 놓을 수 없음
        if (r1 - c1 == r2 - c2) return true; // 체스 배열의 특성상 퀸의 위치에서 우측 위로 좌측 아래로의 대각선은 행에서 열을 뺀 수의 자리이다 그렇기 때문에 값이 같다면 공격이 가능한 위치에 있다는 것
        if (r1 + c1 == r2 + c2) return true; // 체스 배열의 특성상 퀸의 위치에서 우측 아래로 좌측 위로의 대각선은 행에서 열을 더한 수 의 자리이다 그렇기 때문에 값이 같다면 공격이 가능한 위치에 있다는 것
        return false;
    }
 static void dfs(int row) {
        if (row == N + 1) { //  퀸을 다 놓으면 ans ++
            ans++;
        } else {
            for (int c = 1; c <= N; c++) {
                boolean possible = true; // 완전탐색을 줄이기 위해 공격당하는 자리에 퀸이 놓이게 된다면 반복문을 중지시켜서 그 뒤로 탐색을 하지않아도 되게 하기 위해 possible을 이용하여 for문을 break하게 해준다.
              
                for (int i=1;i<=row-1;i++){
                    // (i, arr[i])
                    if (attackable(row, c, i, arr[i])){ //공격가능한 자리에 퀸이 놓였는지 attackable 함수를 사용하여 확인
                        possible = false; //퀸이 공격당하는 위치에 놓여있다면 
                        break;            //  break을 통해 for문 중단 ( 탐색 시간을 줄여줌 ) 
                    }
                }
                if (possible) { //제대로 퀸을 공격을 당하는 위치가 아니라면 그 뒤로도 가능한 자리를 탐색
                    arr[row] = c;
                    dfs(row + 1);
                    arr[row] = 0;
                }
            }
        }
    }
}