[NQUEEN] N-Queen
개발이야기/알고스팟2022. 1. 4. 16:48
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] != 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;
}
}
}
|
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 |