[Gold IV] N-Queen - 9663
성능 요약
메모리: 14468 KB, 시간: 5260 ms
분류
백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing)
문제 설명
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
참고 https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-9663%EB%B2%88-java
너무 정리를 잘해둔 벨로그가 있어서 참고하였다.
4X4 기준 arr[0], arr[1], arr[2], arr[3] 은 왼쪽에서부터 각 열(세로줄)을 의미하고
arr[0] = 0 , arr[0] = 1, arr[0] = 2, arr[0] = 3 은 그 세로줄에 둘 수 있는 비숍의 위치를 의미한다. (0,0), (0,1), (0,2), (0,3)
결국 depth = 0인 때부터 (arr[0]) 첫 위치에 따른 나머지 모든 자리에 비숍을 둘 수 있는 방법을 탐색해 나가는 전체 경우의 수 따지기인데,
2차원을 1차원으로 옮겨 표현해야하니 처음에는 좀 이해하기 쉽지 않다.
depth가 진행되면서 비숍을 놓을 수 있는 자리인가 validation 하는 방법도 지금 놓으려는 줄 이전에 왔던 모든 세로줄에 두어져 있는 비숍들과 위치를 파악해야한다는 것도 신선하다. (애초에 세로로 진행해본게 거의 드물다)
상식적으로 두 비숍의 가로와 세로의 차의 절대값이 같으면 (가로 1, 세로 1, 가로 2, 세로 2 등 차이가 나면) 대각선이라는 측정도 혼자 생각해내기 쉽지 않았다.
- 왼쪽부터 오른쪽으로 열 차례로 진행하면서 하나 두고, 오른쪽에 둘 수 있는 공간 찾으면서 하나씩 두고, 4X4 기준,
4개를 모두 두게 되는 경우의 수를 카운팅한다.
코드
public class Main {
static int[] arr;
static int N;
static int result = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
nQueen(0);
System.out.println(result);
}
//arr[depth열] = 값(행) ex) arr[0] = 1 (0,1)에 체스가 위치
static void nQueen(int depth) {
//depth +1 될 때 마다 왼쪽에서 오른쪽으로 진행이다. 전체 진행 완료란 의미
if (depth == N) {
result++;
return;
}
//depth (열) 별로 한 줄씩 체스를 둘 수 있는지 check
for (int i = 0; i < N; i++) {
arr[depth] = i;
if (Possibility(depth)) {
nQueen(depth +1);
}
}
}
static boolean Possibility(int depth) {
//현재 세로줄에서 놓을 수 있는 위치를 확인해야 하니까
//그 이전 줄들까지 두었던 체스말들 (arr[0~depth-1] 값들)과 가로줄, 대각선 비교
for (int i = 0; i < depth; i++) {
if (arr[depth] == arr[i]) {//이전 체스말들 (arr[i]과 지금 둘 수 있는지 확인하는 위치가 가로줄이 맞으면 못둠
return false;
}else if(//내가 두고자 하는 위치와 이전에 두어졌던 체스말들과 가로행, 세로행의 차 절대값이 같으면 대각선
Math.abs(depth - i) == Math.abs(arr[depth] - arr[i])) return false;
}
return true;
}
}