공간 복잡도를 고려했을 때, 1 <= N < 15 이므로 N에 대한 type 은 int 를 사용하겠다.
[시간 복잡도]
해당 문제는 말을 놓을 수 있는 경우의 수는 N X NPN 이 될 것이고 좌표를 검증하는 로직에 대해서는 N 제곱이 될 것이다.
이러한 것들을 감안하여 코드를 작성하겠다.
# Process
기능을 담당하는 함수들을 모듈화 해서 작성했다.
main
: main 에서는 N을 입력받고, 1 .. N까지의 y좌표를 입력할 Ches 라는 배열을 생성한다.
ans 는 경우의 수를 의미한다.
static int N;
static int[] Ches;
static int ans;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Ches = new int[N+1];
}
recursion
: 좌표를 탐색하는 재귀함수 로직이다. row(x좌표)를 차례대로 탐색하며 N+1까지 좌표를 모두 찍었다면 ans 에 값에 +1 해준다. 1 .. N+1 까지 모든 좌표를 탐색하는 과정에서 현재보다 이전 좌표들을 탐색하며 row, c 에 말을 둬도 되는 지에 대한 함수를 통해 validation check 를 진행한다.
해당 함수를 통해 그 좌표에 말을 둬도 된다면 말을 두고 그 다음 열을 탐색한다. 탐색을 한 뒤에는 해당 좌표를 다시 0으로 초기화 해주는 것을 잊어서는 안된다.
static void rec_func(int row)
{
// [N+1까지 모두 탐색]
// N+1까지 좌표를 모두 찍었다면 count
if(row == N+1)
{
ans++;
}
else
{
// [1-N까지 탐색하는 로직]
// row(현재열), 1 .. N 까지 탐색
for(int c=1; c<=N; c++)
{
boolean possible = true;
// [row,c 검증]
// 현재보다 위에 찍힌 좌표들을 확인하여 row, c 를 찍어도 되는 지 확인
for(int i=1; i<=row-1;i++)
{
// int r1, int c1, int r2, int c2
if(attackable(row, c, i, Ches[i]))
{
possible = false;
break;
}
}
// 찍어도 된다면 찍고 다음칸으로 이동
if(possible)
{
Ches[row] = c;
rec_func(row+1);
Ches[row] = 0;
}
}
}
}
attackable
: 해당 함수는 두 좌표에 대한 공격 가능함을 판단하는 기능을 한다.
r1, c1, r2, c2 를 인자로 받는데 (r1, c1) 와 (r2, c2) 의 좌표를 의미한다.
고려해야 할 사항은 같은 아래 3가지 사항이다.
1. 같은 열인지
2. 왼쪽 대각선 상에 존재하는 지
3. 오른쪽 대각선 상에 존재하는 지
static boolean attackable(int r1, int c1, int r2, int c2)
{
// (r1,c1) (r2,c2)
// 같은 y열
if(c1 == c2) return true;
// 왼쪽 대각선
if(r1-c1 == r2-c2) return true;
// 오른쪽 대각선
if(r1+c1 == r2+c2) return true;
return false;
}
Code
: 전체 코드 첨부
import java.io.*;
import java.util.*;
public class Main
{
static int N;
static int[] Ches;
static int ans;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Ches = new int[N+1];
rec_func(1);
System.out.println(ans);
}
static void rec_func(int row)
{
// [N+1까지 모두 탐색]
// N+1까지 좌표를 모두 찍었다면 count
if(row == N+1)
{
ans++;
}
else
{
// [1-N까지 탐색하는 로직]
// row(현재열), 1 .. N 까지 탐색
for(int c=1; c<=N; c++)
{
boolean possible = true;
// [row,c 검증]
// 현재보다 위에 찍힌 좌표들을 확인하여 row, c 를 찍어도 되는 지 확인
for(int i=1; i<=row-1;i++)
{
// int r1, int c1, int r2, int c2
if(attackable(row, c, i, Ches[i]))
{
possible = false;
break;
}
}
// 찍어도 된다면 찍고 다음칸으로 이동
if(possible)
{
Ches[row] = c;
rec_func(row+1);
Ches[row] = 0;
}
}
}
}
// 좌표를 찍을 때 공격 가능 여부를 확인
static boolean attackable(int r1, int c1, int r2, int c2)
{
// (r1,c1) (r2,c2)
// 같은 y열
if(c1 == c2) return true;
// 왼쪽 대각선
if(r1-c1 == r2-c2) return true;
// 오른쪽 대각선
if(r1+c1 == r2+c2) return true;
return false;
}
}