문제 링크: https://www.acmicpc.net/problem/9663
참고: https://st-lab.tistory.com/118
퀸은 그림처럼 상하좌우 및 대각선으로 거리 제한없이 한 방향으로 이동할 수 있다.
4X4 크기의 체스판에서 퀸이 움직일 수 있는 것은 다음과 같다.
두번째 열에서 빈 공간은 첫번째만 해당되고, 퀸이 이동할 수 있는(=공격 가능한) 경로에 모두 X 표시한다.
세번째 열에서 빈 공간은 4번째만 해당되고, 역시 퀸이 이동할 수 있는(=공격 가능한) 경로에 모두 X 표시한다.
네번째 열에서 빈 공간은 첫번째만 해당되고, 이동 가능한 경로를 모두 탐색했으니 탐색 가능한 경우의 수를 1 업데이트하고 종료한다.
위의 과정을 재귀적으로 호출하여, 이동하고 모두 배치하면 경우의 수로 더해준다.
구현해야할 것은 다음과 같다.
1. 어떻게 말을 움직이고, 재귀 호출할 것인가
2. 퀸을 놓을 수 있는 여부를 판단할 수 있는 방법은 무엇인가?
우리는 1차원 배열을 사용할 것이다.
즉 index는 퀸이 놓인 열이 되고, 원소값은 퀸이 놓인 행이 된다.
배열이 0부터 시작되는 것을 고려하여, 그림을 1차원 배열로 나타내면 [2, 0, 3, 1]
이 된다.
이렇게 첫번째열부터 하나씩 채워나가고, 놓일 수 있는 위치이면 재귀호출을 한다.
퀸을 놓을 수 있는지 아닌지는 어떻게 판단하는 것일까?
해당 열의 행과 i열의 행일 일치하는지 확인한다.(같은 행에 존재하는 경우)
열의 차와 행의 차가 같은지 확인한다.(대각선에 놓인 경우)
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n;
static boolean[] visited;
static int[] arr;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
n = Integer.parseInt(br.readLine());
visited = new boolean[n];
arr = new int[n];
nQueen(0);
sb.append(count);
System.out.println(sb);
}
private static void nQueen(int depth) {
// 모든 원소를 다 채운 상태면 count를 증가하고 return한다.
if (depth == n){
count += 1;
}
// 시작점을 0부터 N-1까지 바꿔가면서 value를 변경한다.
for(int i = 0; i < n; i++){
if(visited[i]){
continue;
}
arr[depth] = i;
if(togo(depth)){
visited[i] = true;
nQueen(depth + 1);
visited[i] = false;
}
}
}
// 놓을 위치가 다른 퀸으로부터 위협받는가
private static boolean togo(int depth) {
for(int i = 0; i < depth; i++){
// 해당 열의 행과 i영의 행이 일치하는 경우: 같은 행에 존재하는 경우
if(arr[i] == arr[depth]){
return false;
}
// 열의 차와 행의 차가 같으면 대각선에 놓인 경우: 대각선에 놓인 경우
else if (Math.abs(depth-i) == Math.abs(arr[depth]-arr[i])){
return false;
}
}
return true;
}
}
체스를 잘 몰라서 일단 어려웠다.
체스판이라서 처음에 2차원 배열로 풀었는데 인덱스의 배열이 인덱스가 있다는 점을 이용해 1차원 배열로 풀이한 것이 흥미로웠다.
추가로 알 수 있는 내용!
visited 배열을 사용하여 방문 표시를 하면, 시간을 단축할 수 있다.
+) python에서는 visited 배열이 없으면 시간 초과가 난다!
자바에서 visited 배열 없으면 5292ms나오고, visited 배열 있으면 3812ms 나온다.