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

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

 

algospot.com :: NQUEEN

N-Queen 문제 정보 문제 N-Queen 퍼즐은 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 퍼즐이다. (퀸은 체스에서 가장 강력한 기물로, 자신의 위치에서 상하좌우, 그리고 대각선

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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] != 0continue;
            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;
        }
    }
}
cs


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

 

[PICNIC] 피크닉


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

 

 

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

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
[SHISENSHO] Shisen-sho  (0) 2022.01.03
Posted by N'