[백준`G4] 9663 - N-Queen (Java)

문제 설명

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

 

 

성능 요약
메모리: 14468 KB, 시간: 6084 ms

 

분류
백트래킹, 브루트포스 알고리즘

 

문제 설명
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

---

문제 풀이

보드가 이차원 배열이기 때문에 배열을 받을 때 2차원 배열로 해도 되지만, 1차원 배열로도 가능하다.

각 원소의 index를 행이라고 생각하고, 원소값을 열이라고 생각하면 1차원 배열로도 가능하다.

예를 들어, arr = [1, 3, 0, 2] 면 다음과 같다.

	o
			o
o
		o

 

이렇게 1차원 배열로도 구현할 수 있다.

 

 

대각선 확인

각 좌표의 행을 뺀 절댓값 == 각 좌표의 열을 뺀 절댓값

• 🍕 : (1, 2)와 (3, 0)일 때, abs(1 - 3) == abs(2 - 0)
• 🍗 : (0, 1) 과 (2, 3)일 때, abs(0 - 2) == abs(1 - 3)

	🍗
		🍕
			🍗
🍕

 

 

arr[depth] = i 에서 0, 1, 2, 3이 차례대로 대입되면서 열의 위치를 정한다.

만약 possible(depth)가 true면 == 해당 행(depth)과 해당 열(i)에 퀸을 놓을 수 있으면

재귀로 nQueen(depth + 1)을 호출하여 다음 행을 탐색한다.

 

만약 possible(depth)가 false면 == 해당 행(depth)과 해당 열(i)에 놓을 수 없다면 

nQueen 함수가 호출되지 않고, i++로 다음 열 번호로 넘어가면서 다음 열에 퀸을 놓는 경우를 탐색하게 된다.

 

이렇게 계속 탐색하다가 depth가 N이 되면 == 맨 아래 행까지 퀸을 놓았다면

count ++로 수를 증가시켜 준다.

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

public class Main {

    public static int N = 0;
    public static int[] arr;
    public static int count = 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];

        nQueen(0);
        System.out.println(count);

    }

    public static void nQueen(int depth) {
        if (depth == N) {
            count++;
            return;
        }

        for (int i = 0; i < N; i++) {
            // 0 1 2 3 이 차례로 대입되면서 열의 위치를 정한다.
            arr[depth] = i;
            // 놓을 수 있으면 다음 행 탐색
            if (possible(depth)) {
                nQueen(depth + 1);
            }
        }
    }

    public static boolean possible(int depth) {
        for (int i = 0; i < depth; i++) {
            // 세로 확인
            if (arr[depth] == arr[i]) {
                return false;
            }

            // 대각선 확인
            else if (Math.abs(depth - i) == Math.abs(arr[depth] - arr[i])) {
                return false;
            }
        }
        return true;
    }
}