※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
힌트
여덟 퀸 문제란?
여덟 퀸 문제란 1848년 막스 베첼이 처음 제안한 문제로, 8×8 사이즈의 체스판 위에 8개의 퀸을 놓되 각 퀸들은 서로를 공격할 수 있어서는 안되도록 배치해야한다.
난 체스를 몰라서 찾아보니 퀸의 경우에는 체스판에서 상하좌우 및 대각선 방향으로 거리에 상관없이 이동이 가능하다고 한다. 사기캐 아닌가?
어쨌든 위의 조건을 이용하여 체스판 위에 각 퀸들의 진로에 서로 겹치지 않도록 퀸을 배치해야한다.
즉 N-Queen 문제는 NxN 크기의 체스판에 N개의 퀸을 위 조건에 따라 놓는 문제인 것이다.
풀이
백트래킹을 이용해서 푼다.
제일 윗 행부터 아래로 한 줄씩 내려가면서 각 줄에서의 퀸의 위치를 찾을 것이다. 조건에 의해 한 줄에는 퀸이 한개만 올 수 있으니 각 줄마다 한 개의 퀸만 두면 된다.
먼저 0행의 0번째 자리에 퀸을 두고 놓을 수 있는지 검사한다. 지금은 판 위에 퀸이 하나밖에 없으니 당연히 가능.
이후 1행의 0번째 자리에 퀸을 두고 다시 검사한다. 바로 위에 퀸이 있으니 불가능. 그럼 바로 옆칸으로 옮겨서 또 검사한다… 이걸 반복하는 것이다.
마지막 행까지 퀸을 놓았다면 경우의 수를 저장할 변수를 +1하고 이전 케이스로 돌아가서 또 탐색하며 가능한 모든 경우의 수의 개수를 찾으면 된다.
public static int N; // 입력받은 N을 전역변수로 취급. 이유는 매개변수로 안넘기려고
public static int[] arr; // 판에 둔 퀸의 좌표 저장. 인덱스가 행, 값이 열을 의미
public static int answer = 0; // 경우의 수 카운트용 변수
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
N = Integer.parseInt( br.readLine());
arr = new int[N]; // N개의 퀸을 둬야하므로 크기를 N으로
findQueen(0); // 0번 행부터 퀸 찾기 시작
sb.append(answer); // 전부 찾은 후 경우의 수 출력
System.out.println(sb.toString());
br.close();
}main 함수는 간단하다. findQueen() 함수로 퀸 찾기를 시작한다.
public static void findQueen(int y){
if(y == N){ // 마지막 행까지 다 둔다음 다시 호출되면 경우의 수+1 하고 리턴
answer++;
return;
}
// 현재 줄(행)에서 왼쪽부터 오른쪽 끝까지 자리에 대해 둘 수 있는지 검사
for(int x=0; x<N; x++){
arr[y] = x; // 현재 줄의 x번 칸에 퀸을 뒀다 가정
if(allowQueen(y)){ // y줄 x번 칸에 퀸 두기가 가능한지 검사
findQueen(y+1); // 가능하면 다음줄로 넘어간다
} // 불가능하면 다음 옆자리로 넘어감
// 끝까지 다 불가능하면 이전 호출로 가서 이전 줄에서 위치를 옮김
}
}현재 행에 대해서 0번부터 N-1번 자리까지 순차적으로 퀸을 두었다고 가정한 후 그 자리에 퀸을 두는 것이 가능한지 allowQueen() 함수로 검사한다.
가능하면 그대로 다음 줄로 가면 되고, 안되면 옆자리로 옮겨서 또 검사한다. 만약 끝까지 불가능하면 이전에 두었던 위치가 틀린 것이므로 그대로 함수를 나가서 이전으로 돌아간다.
public static boolean allowQueen(int y){
int x = arr[y];
for(int i=0; i<y; i++){ // 제일 윗줄부터 현재줄 이전까지 퀸의 위치를 바탕으로 검사
int qx = arr[i];
int qy = i;
// 현재 검사중인 퀸의 x좌표와 현재 둔 퀸의 x좌표가 같으면 바로 아래이므로 불가
// 검사퀸과 둔퀸의 행과 열 각각의 차가 같으면 대각선이라 불가
if((x == qx) || (Math.abs(qx-x) == Math.abs(qy-y))){
return false;
}
}
return true;
}매개변수로 넘어온 y 행에 대해서 그 행에 둔 퀸이 그 자리에 둘 수 있는지 확인한다. 위에서 arr의 인덱스 y에 x를 값으로 저장했으므로 y행의 퀸이 몇 번째 자리(x)인지를 배열 arr에서 가져올 수 있다.
제일 윗 줄부터 현재 줄의 바로 윗줄까지 검사를 한다. qx는 qy행에 두었던 퀸의 x좌표이다.
만약 현재 줄의 퀸과 검사중인 줄의 퀸의 x좌표가 같다는 것은 현재 줄의 퀸의 바로 위에 또 퀸이 있다는 뜻이므로 불가능하다.
또한 대각선에 대해서도 검사해야되는데, x는 x끼리, y는 y끼리 차이의 절댓값이 같으면 대각선상에 존재한다는 뜻이므로 마찬가지로 퀸을 둘 수 없다.
이러한 것을 반복하면서 끝까지 퀸을 채울 수 있는 경우를 찾아나간다.
댓글