[알고리즘] 백준 9663번 - N-Queen(Java)

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

 

* 풀이

N-Queen 문제는 가장 대표적인 백트래킹 문제다. 해당 문제를 풀기 위해서는 먼저 3가지 과정을 살펴보아야 한다.

1. 1차원 배열을 생성한다.(배열의 index는 열에 해당함. 배열의 value는 행에 해당함.) dfs를 하며 백트래킹 진행

- ex) {3} -> index : 0, value : 3 -> 3행 0열

2. 열 단위로 반복문을 진행하는데, 퀸을 놓을 수 있는 자리인지 확인한다.(isPossible 메서드) 확인하여 퀸을 놓을 수 있는 자리라면 true를 반환하고, 퀸을 놓을 수 없는 자리라면(같은 행인 경우, 대각선 위치에 있는 경우) false를 반환한다.

 

* 같은 행인 것을 확인하는 방법 : i열(index)만큼 반복 -> chessArray[column] == chessArray[i] 이라면(i열 행과 column열의 행과 같다면 -> value가 행이므로) 같은 행에 존재한다.

 

* 대각선 위치에 있는 것을 확인하는 방법 : (index의 값 - index의 값) == (value의 값 - value의 값) 이라면 대각선 위치에 존재한다.

 

3. 퀸을 놓을 수 있는 자리라면 column을 1씩 증가시켜 dfs를 진행한다. column이 최대 크기 n과 같아진다면 경우의 수인 count를 증가시킨다.

 

다음은 풀이 코드이다.

import java.util.*;

public class Main {
    static int count = 0;
    static int[] chessArray;
    
    public static void dfs(int column, int n) {
        if(column == n) {
            count++;
            return;
        }

        for(int i = 0; i < n; i++) {
            chessArray[column] = i;

            if(isPossible(column)) {
                dfs(column + 1, n);
            }
        }
    }

    public static boolean isPossible(int column) {
        for(int i = 0; i < column; i++) {
            if(chessArray[column] == chessArray[i])
                return false;
            
            else if(Math.abs(column - i) == Math.abs(chessArray[column] - chessArray[i]))
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        chessArray = new int[n];

        dfs(0, n);
        System.out.println(count);
    }
}