[프로그래머스] Level 2 : N-Queen(Java)

문제 링크

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

프로그래머스

---

💡 풀이

N-Queen 문제는 행렬에 퀸을 놓았을 때, 서로 공격할 수 없는 상태가 되도록 배치하는 문제로, 전형적인 백트리킹 알고리즘입니다.

문제를 분석해보면 다음과 같습니다. 

• 퀸은 하나의 행에 하나만 존재할 수 있다.
  • 즉, 재귀함수 탐색의 기준(depth)으로 사용할 수 있습니다.
• 마지막 행에 퀸 배치를 성공한다면, 가능한 경우의 수가 하나 증가한다.
• 불가능한 경우는 탐색을 중단해 가지치기 한다. 

보통 체스판이나 그래프의 경우 2차원 배열을 주로 사용합니다. 하지만, 이 문제에서는 한 행에 1개의 퀸만 존재할 수 있다는 조건이 있습니다. 따라서 1차원 배열만으로 퀸의 위치를 표현할 수 있습니다.

코드로 설명을 해보면,

queen[row][col] = true;

원래 위의 코드와 같이, 2차원 배열을 통해 퀸이 존재하는 것을 표현했다면, 이 문제는 아래와 같이 1차원 배열로 표현할 수 있게 되는 것입니다. 

queen[row] = col;

물론, 한 행에 1개의 퀸만 존재할 수 있다는 조건이 있기에 가능한 방법입니다. 

 

백트래킹

다음으로 아래와 같은 백트래킹 구조로 나눌 수 있습니다. 

 

Base Case

재귀 함수가 마지막 행에 퀸을 배치한 경우

0번 째 행부터 순서대로 모든 경우의 수를 가지치며 카운트 합니다. 

// n : 가로 세로의 길이, row : 현재 행
if(row == n) {
    return 1;
}

Recursive Case 

0 ~ (n - 1) 열을 돌며 퀸 배치를 시도

Backtrack

체스 룰에 위배된다면 퀸을 배치할 수 없도록 막기

이때, 체스 룰에 위배되는지 확인하는 코드는 다음과 같습니다. 

static boolean isValid(int row, int col) {
    for(int index = 0; index < row; index++) {
        // 열 확인
        if(queen[index] == col) {
            return false;
        }

        // 대각선 확인
        if(Math.abs(row - index) == Math.abs(col - queen[index])) {
            return false;
        }
    }
    return true;
}

반복문이 row를 돌며 해당하는 col에 퀸이 있다면(queen[index] == col), 같은 열에 퀸이 있다는 뜻이므로 false를 반환합니다. 또, 대각선 확인 부분을 살펴보면, 대각선 좌표는 (row, col) 좌표로 부터 같은 스칼라만큼 떨어져 있습니다. (row, col)에서 같은 수를 더하거나 빼야 대각선에 위치하게 되는 것이죠. 따라서, 절댓값을 씌워 행과 열의 차이가 같은지 체크하면, 대각선 상에 존재하는지 확인할 수 있습니다. 

 

전체 코드

위 과정을 종합한 전체 코드는 다음과 같습니다. 

class Solution {
    static final int MAX_ROW = 12;
    static int[] queen = new int[MAX_ROW + 1];
    
    public int solution(int n) {
        int answer = 0;
        
        answer = recur(n, 0);
        
        return answer;
    }
    
    static int recur(int n, int row) {
        int count = 0;
        
        // Base Case 
        if(row == n) {
            return 1;
        }
        
        for(int col = 0; col < n; col++) {
            if(isValid(row, col)) {
                queen[row] = col;
                count += recur(n, row + 1);
            }
        }
        
        return count;
    }
    
    static boolean isValid(int row, int col) {
        for(int index = 0; index < row; index++) {
            // 열 확인
            if(queen[index] == col) {
                return false;
            }
            
            // 대각선 확인
            if(Math.abs(row - index) == Math.abs(col - queen[index])) {
                return false;
            }
        }
        
        return true;
    }
}