[NQUEEN] N-Queen

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/NQUEEN

algospot.com :: NQUEEN

풀이입니다. 🤔

import java.util.*;
 
public class Main {
    private static final int[][] boards = new int[12][12];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt();
            System.out.println(getCount(n, 0));
        }
    }
 
    private static int getCount(int n, int y) {
        if (y >= n) return 1;
        int ret = 0;
        for (int x = 0; x < n; ++x) {
            if (boards[y][x] != 0) continue;
            put(n, y, x, 1);
            ret += getCount(n, y + 1);
            put(n, y, x, -1);
        }
 
        return ret;
    }
 
    private static void put(int n, int y, int x, int count) {
        boards[y][x] += count;
        for (int i = 1, len = n - y; i < len; ++i) {
            boards[y + i][x] += count;
            if (x - i >= 0) boards[y + i][x - i] += count;
            if (x + i < n) boards[y + i][x + i] += count;
        }
    }
}

이 풀이는 기존에 풀었던 아래 문제와 유사합니다. 

 

[PICNIC] 피크닉

재귀로 행마다 하나의 퀸을 배치해보면 총 경우의 수를 구할 수 있습니다. 
같은 경우의 수를 방지하기 위해, 아래 행을 향하여 공격범위를 기록하며 위에서 아래 행으로만 가짓수를 세도록 합니다.

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️