백준 9663. N-Queen 문제

 

알고리즘

모든 경우를 전부 시도해 보아야 한다. 단, Queen을 놓을 수 없는 위치라고 판단되면 중지하고 다음 경우의 수를 시도해볼 수 있다.

-> 백트래킹

 

접근방법

• 모든 경우의 수를 전부 확인해야 하는 문제이다
• 2차원 배열이 아닌 1차원 배열로 문제를 풀어내 구현의 난이도를 낮출 수 있다.
  • 4x4 N-Queen 보드에 (0, 0), (1, 3), (2, 1), (3, 2) 위치에 Queen 을 놓는다고 할 때, 1차원 배열로 다음과 같이 표현 가능하다.
    
    1차원 배열 : [0, 3, 1, 2] => 행은 index, 열은 값으로 표현

 

코드

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

public class Main {

    private static int N;
    private static int[] array;
    private static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        array = new int[N];

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

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

        for (int i = 0; i < N; i++) {
            array[depth] = i;

            if (isPossible(depth)) {
                nQueen(depth + 1);
            }
        }
    }

    private static boolean isPossible(int col) {
        for (int i = 0; i < col; i++) {
            // 행이 같은지
            if (array[col] == array[i]) {
                return false;
            }

            // 대각이 같은지
            if (Math.abs(col - i) == Math.abs(array[col] - array[i])) {
                return false;
            }
        }

        return true;
    }
}