1. 문제 및 조건
문제
크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
2. 설명
N-Queen을 구하기 전에, 체스에서 퀸이 공격할 수 있는 자리는 퀸을 기준으로 한 직선 상의 모든 곳과 대각선 상의 모든 곳을 공격할 수 있는 말입니다.
공격할 수 없게 놓는 경우의 수를 구하는 흐름은 다음과 같습니다.
첫 번째 행에 1열 퀸을 놓는다.
두 번째 행에서 공격 받지 않는 자리는 3, 4열이 있는데, 3열에 우선 퀸을 놓습니다.
세 번째 행에서 공격 받지 않는 자리가 없기 때문에 두 번째 행으로 돌아갑니다.
두 번째 행에서 4열에 퀸을 놓습니다.
세 번째 행에서 공격 받지 않는 곳은 2열 밖에 없기 때문에 2열에 놓습니다.
네 번째 행에서 공격 받지 않는 열이 없기 때문에 이전 탐색으로 돌아가는데, 세 번째와 두 번째 행에서 놓을 수 있는 열을 전부 거쳐왔기 때문에 첫 번째 행으로 돌아갑니다.
첫 번째 행에서 2열에 퀸을 놓습니다.
두 번째 행에서 공격 받지 않는 자리는 4열 밖에 없기 때문에 4열에 퀸을 놓습니다.
세 번째 행에서 공격 받지 않는 자리는 1열 밖에 없기 때문에 1열에 퀸을 놓습니다.
네 번째 행에서 공격 받지 않는 자리는 3열 밖에 없기 때문에 3열에 퀸을 놓습니다. 이로써 4개의 퀸이 모두 놓여졌기 때문에 경우의 수를 카운팅합니다.
위와 같은 방식으로 첫 번째 행의 퀸이 4열에 놓일 때 까지 반복합니다.
3. 해결 방식
퀸은 직선 상의 모든 말을 공격할 수 있기 때문에, 한 행에 퀸은 하나만 들어갈 수 있습니다. 따라서, 한 행에 하나의 위치 정보만 저장 할 수 있기 때문에 int arr[n] 형식의 1차원 배열에 위치를 저장하는 방식을 채택했습니다.
검사 행 인덱스는 이전 행 인덱스보다 항상 큽니다.
1과 같은 이유로, 이전의 위치 정보와 같은 위치 정보를 넣으려고 한다는 것은 퀸의 직선 상에 놓는 것이기 때문에 arr[이전 행 인덱스] == arr[검사 행 인덱스]일 경우 건너뜁니다.
이전의 위치 정보와 대각선 상에 놓으려는 것은 건너뜁니다. 대각선 상에 위치한다는 것은, (이전의 말 x좌표 - 검사 위치 x좌표) 절대값 == (이전의 말 y좌표 - 검사 위치 y좌표) 절대값 이라는 규칙이 있고, 2번 규칙으로 인해 arr[이전 행 인덱스] - arr[검사 행 인덱스] 의 절대값 == 검사 행 인덱스 - 이전 행 인덱스 라는 식으로 검사합니다.
4. 코드
import java.util.Scanner;
class Main {
static int count = 0;
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] col = new int[n]; // 각 행에 위치할 퀸의 위치 정보를 저장할 배열
for(int i=0;i<n;i++) {
col[0] = i;
nqueen(0,col);
}
System.out.println(count);
input.close();
}
public static boolean rule(int index, int col[]) {
int k = 0;
while(k < index) {
if(col[k] == col[index] || Math.abs(col[k] - col[index]) == index - k) {
return false;
}
k++;
}
return true;
}
public static void nqueen(int index, int[] col) {
if(rule(index,col)) {
if(index == col.length-1) {
count++;
}
else {
for(int i=0;i<col.length;i++) {
col[index + 1] = i;
nqueen(index+1,col);
}
}
}
}
}
Comments