[프로그래머스] 12952 - N-Queen

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

문제 파악

N * N의 체스판에서 N개의 퀸을 놓을 수 있는 경우의 수를 리턴

 

어려운 점

시간 초과가 나지 않게 구현하도록 하자.

재귀로 구현하게 될 것 같은데 시간 복잡도가 높아지지 않는 방법을 생각해 내기가 어려웠다.

 

풀이

int 배열을 생성하여

• index -> column
• index애 해당하는 값 -> row

로 지정하여 구현하면 일차원 배열로도 구현 가능하다.

n개의 퀸을 필수적으로 놓아야 하므로,

• column(= queen의 개수)을 높여 가며 퀸의 개수가 N에 도달하는 경우에 경우의 수를 늘려 준다.
  
  • 이 때, column을 늘려 간다는 뜻은 column-1 에 해당하는 칸까지 무사히 퀸을 놓았다고 볼 수 있다.
• 현재 column에 row를 변화시키며 체스판에 변화를 주고, column-1까지의 퀸에 당하지 않는 경우 재귀호출하도록 한다

 

코드

static int[] arr;
static int answer;
static int N;

public static int solution(int n) {
    N = n;
    arr = new int[N];
    backTracking(0);
    return answer;
}

public static void backTracking(int depth) {
    if (depth == N) {
        answer++;
        return;
    }
    for (int i = 0; i < N; i++) {
        arr[depth] = i;
        if (available(depth)) {
            backTracking(depth + 1);
        }
    }
}

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