https://www.acmicpc.net/problem/9663
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n;
static int[] col;
static int cnt = 0;
static boolean check(int y) {
for (int i = 0; i < y; i++) { // y행 이전의 행들 비교
if (col[y] == col[i] || Math.abs(y - i)==Math.abs(col[y] - col[i])) // 같은 열에 퀸이 있거나 대각선에 있으면
return false;
}
return true;
}
static void dfs(int y) {
if (y == n) { // n번째 행까지 퀸 n개를 다 놓았다면
cnt++;
return;
}
for (int i = 0; i < n; i++) {
col[y] = i; // y번째 행의 i번째 열에 퀸을 배치
if (check(y)) dfs(y + 1); // 놓을 수 있다면 다음 행에 퀸 배치
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
col = new int[n]; // col[index] = n --> index번째 행의 n번째 열에 퀸이 있음
dfs(0);
System.out.println(cnt);
}
}
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 2580번- 스도쿠 (0) | 2023.01.06 |
---|---|
[JAVA] 백준 16198번- 에너지 모으기 (0) | 2023.01.04 |
[JAVA] 백준 11663번- 선분 위의 점 (0) | 2022.12.30 |
[JAVA] 백준 2512 - 예산 (0) | 2022.12.30 |
[JAVA] 백준 2343 - 기타 레슨 (0) | 2022.12.29 |