[BOJ] N-Queen

문제

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

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

풀이

백트래킹의 아주 유명한 문제이다.
전공수업중 인공지능 수업때 이를 다룬적이 있었는데 배경지식이 있다보니 설계 자체는 어렵지 않게 할 수 있었다.

퀀은 행, 렬, 대각선 이동이 모두 가능하다.
따라서 모든 퀸은 행, 렬, 대각선 상에서 모두 다른 위치에 있어야 한다.

첫번째 퀸이 첫 행에서 열의 위치를 잡는다.
두번째 퀸이 두번째 행에서 행의 위치를 잡는다.

이때 이전의 위치한 퀸과 행, 렬, 대각선 위치를 검사

위치가 겹친다면 열을 한칸 이동해서 다시 검사

검사시 겹치지 않는다면 그 다음 퀸도 같은 작업

이 순서로 백트래킹을 구현하면 된다.

이때 검사시 행은 겹칠수가 없으므로 열과 대각선만 검사한다.
만든 arr 배열은 각 행에 위치칸 퀸의 열을 값이다.
행의 감사는 배열 값만 검사하면 된다.

대각선의 검사는 행과 열을 뺀 절댓값이 같은 값이면 된다.

따라서 다음과 같은 조건식을 세워준다.

static boolean check(int\[\] arr, int depth) {    // depth: 컬럼  
        for(int i = 0; i < depth; i++) {  
            if (arr\[i\] == arr\[depth\]   
                || Math.abs(depth - i) == Math.abs(arr\[depth\] - arr\[i\])) {  
                return false;  
            }   
        }  

        return true;  
    }  

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

public class Main{
    static int N;
    static int count;
    public static void main(String[] args) throws IOException{
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(rd.readLine());
        int[] arr = new int[N];
        play(arr, 0);
        System.out.println(count);
    }

    static void play(int[] arr, int depth) {    // arr: 퀸의 위치

        if (depth == N) {
            count++;
            return;
        }

        for(int i = 0; i < N; i++) {
            arr[depth] = i;
            if (check(arr, depth)) {
                play(arr, depth + 1);
            }
        }
    }

    static boolean check(int[] arr, int depth) {    // depth: 컬럼
        for(int i = 0; i < depth; i++) {
            if (arr[i] == arr[depth] 
                || Math.abs(depth - i) == Math.abs(arr[depth] - arr[i])) {
                return false;
            } 
        }

        return true;
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/N-Queen