[프로그래머스 Level 3] N-Queen

문제

 

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

 

제한 사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

 

---

풀이

 

아주 유명한 N-Queen 문제다. 백트래킹의 대표 문제라고 할 수 있고, 퀸을 놓을 수 있는 지 체크만 해주면 어렵지 않은 문제다.

 

1. 첫 번째 열에 다음과 같이 놓았다고 가정한다.

 

 

퀸이 위치한 가로/세로/대각선 방향에는 다음 퀸을 놓을 수 없다.

 

 

X표시를 해보면 이렇게 된다.

 

 

2. 다음 열에서 빈 공간은 마지막 행만 가능하다. 즉, 아래 그림처럼 해당 칸에 퀸을 추가한다.

 

 

마찬가지로 놓은 퀸의 이동 경로를 모두 X표시 한다.

 

 

3. 다음 열에서 빈 공간은 첫 번째 행만 가능하다. 즉, 아래 그림처럼 해당 칸에 퀸을 추가한다.

 

 

세 번째 퀸을 놓고나면 빈 칸은 하나만 남게 된다.

즉, 4 x 4 크기의 보드에서 경우의 수 중 하나가 다음과 같다.

 

 

N x N 크기의 보드를 전부 돌다가 한 행에 퀸을 놓고, 다음 행에서 놓는 자리를 구하는 possibility() 메서드가 핵심이라고 할 수 있다.

• board[col] == board[i] : 같은 행에 존재하는 지
• Math.abs(col - i) == Math.abs(board[col] - board[i]) : 행을 뺀 것의 절댓값과 열을 뺀 것의 절댓값이 같으면 대각선에 놓여있는 지 확인한다.

 

public class Solution {
    public static int[] board;
    public static int N, answer;

    public static boolean possibility(int col) {
        for(int i=0; i<col; i++) {
            if(board[col] == board[i]) return false;
            else if(Math.abs(col - i) == Math.abs(board[col] - board[i])) return false;
        }
        return true;
    }

    public static void nQueen(int depth) {
        if(depth == N) {
            answer++;
            return;
        }
        for(int i=0; i<N; i++) {
            board[depth] = i;
            if(possibility(depth)) {
                nQueen(depth + 1);
            }
        }
    }

    public static int solution(int n) {
        board = new int[n];
        answer = 0;
        N = n;

        nQueen(0);

        return answer;
    }
}