[JAVA] 백준 9663. N-Queen

이 글은 읽는데 약 6분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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끼리 차이의 절댓값이 같으면 대각선상에 존재한다는 뜻이므로 마찬가지로 퀸을 둘 수 없다.

이러한 것을 반복하면서 끝까지 퀸을 채울 수 있는 경우를 찾아나간다.

댓글