[D3] N-Queen - 2806
성능 요약
메모리: 20,684 KB, 시간: 170 ms, 코드길이: 1,103 Bytes
제출 일자
2023-10-24 16:19
출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do
문제 해결 방법
1. 놓을 수 있는 경우와 아닌 경우를 구분해야 함
2. 핵심은 대각선 확인하기.(행을 뺀 절대값과 열을 뺀 절대 값이 같으면 대각선 위치)
import java.util.Scanner;
class Solution
{
static int[] arr;
static int n,result;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int tc = 1; tc <= T; tc++)
{
n = sc.nextInt();
arr = new int[n];
result = 0;
nQueen(0);
System.out.println("#" + tc + " " + result);
}
}
private static void nQueen(int depth){
if(depth == n){
result++;
return;
}
for(int i = 0; i < n; i++){
arr[depth] = i;
if(isPossible(depth)){
nQueen(depth+1);
}
}
}
private static boolean isPossible(int col){
for(int i = 0; i < col; i++){
if(arr[col] == arr[i]){
return false;
}
if(Math.abs(i - col) == Math.abs(arr[i] - arr[col])){
return false;
}
}
return true;
}
}
'알고리즘 - SWEA > D3' 카테고리의 다른 글
[SW expert Academy] SWEA 5215번 햄버거 다이어트 자바(Java) (0) | 2023.10.25 |
---|---|
[SW expert Academy] SWEA 2805번 농작물 수확하기 자바(Java) (0) | 2023.10.24 |
[SW expert Academy] SWEA 6730번 장애물 경주 난이도 자바(Java) (1) | 2023.10.24 |
[SW expert Academy] SWEA 4406번 모음이 보이지 않는 사람 자바(Java) (1) | 2023.10.24 |
[SW expert Academy] SWEA 10505번 소득 불균형 자바(Java) (0) | 2023.10.24 |