[Java/백트래킹] Programmers. N-Queen

🤔 Intuition

백트래킹을 학습할 때 주로 다루는 대표 문제임을 이미 알고 접근하긴 했으나,

N이 작은 편이므로 완탐을 우선적으로 고려해볼 만 하다는 점은 분명해 보인다.

 

Queen을 둬보면서 탐색하고, n개의 퀸을 조건에 맞게 배치하는 경우의 수를 모두 탐색하는 건 둬보고, 회귀하여 다시 둬보는 백트래킹으로 가능할 것으로 봤다.

 

개인적으로 생각하기에 이 문제를 푸는 중요 포인트는, 배열을 board 배열을 2차원으로 관리하겠다는 게 사람 입장에서의 관점인데, 항상 1개의 행에 1개의 퀸만 둘 수 있다는 건 자명하므로 이를 1차원으로 운영할 수 있겠다는 아이디어를 캐치하는 것이다.

 

이 문제를 두 번째 푸는 건데도, 처음에는 2차원으로 접근했었다... 아직도 N-Queen 문제가 내 것이 되지 않은 것 같다. 필요한 논리를 세워보고, 배열을 선언할 때 "꼭 이게 2차원이여야 할까? 1차원은 안될까? 3차원은 어떨까?" 하는 고민이 반드시 필요할 것 같다.

🔎 Algorithm & Complexity

@algorithm backtracking
@time O(N^2)
@memory O(N)

👨🏻‍💻 Logic

단순하다. 각 열마다 Queen을 둘 수 있는지 체크한다. 둘 수 있는 경우에 Queen을 두고 다음 열로 이동한다. 그렇게 n개의 Queen을 둔 경우의 수를 센다.

 

다음은 Queen을 둘 수 있는지를 체크하는 로직의 흐름이다.

1. 이전의 행에서 해당 열에 뒀던 적이 있는지 검사한다. (있으면 불가능 : 없으면 가능)

2. 또는 이전 행에서 뒀던 퀸과 현재 두려는 좌표가 대각선상에 있는지 체크한다. (이는 이전 Queen의 좌표와 현재 두려는 좌표의 y거리와 x거리가 같은 경우에 대각선상에 있다고 판단할 수 있음을 이용한다.)

 

위 조건을 통과하는 경우에만 Queen을 배치하고 다음으로 넘어갔다. 백트래킹은 다시 회귀하는 과정이 필요하므로 뒀던 것을 풀어주는 로직이 필요하였다.

class Solution {
    static int ans;
    static int[] row;
    
    public int solution(int n){
        row = new int[n];
        go(0,n);
        
        return ans;
    }
    private void go(int y, int n) {
        if (y == n) {
            ans++;
            return;            
        }
        for (int x = 0; x < n; x++) {
            if (isPromising(y, x, n)) {
                row[y] = x;
                go(y+1, n);
                row[y] = 0;
            }
        }        
        
    }
    private boolean isPromising(int y, int x, int n) {
        for (int i = 0; i < y; i++) {
            if (x == row[i] || Math.abs(x - row[i]) == Math.abs(y - i)) {
                return false;
            }
        }
        return true;
    }
}

 

🏄‍♂️ Other's Idea

더 깔끔하다고 보여지는 로직으로는, 일단 Queen을 배치하고, 그 배치가 문제 없는 경우에만 다음으로 넘어가는 방식으로 로직을 구성한 것이 있었다. 이는 나처럼 Queen 배치를 풀어주는 로직이 없어서 연산을 더 적게 하는 거니까 효율적으로 보인다. 나는 백트래킹을 구성할 때 거의 true + go + false 흐름처럼 재귀 스텝 위/아래로 설정하고 풀어주는 로직을 거의 템플릿처럼 사용하곤 하는데, 이를 조금 더 최적화할 수 있다는 가능성을 배울 수 있었다.

class Solution {
    static int ans;
    static int[] row;
    
    public int solution(int n){
        row = new int[n];
        go(0,n);
        
        return ans;
    }
    private void go(int y, int n) {
        if (y == n) {
            ans++;
            return;            
        }
        for (int x = 0; x < n; x++) {
        	// 나와 다른 부분
            row[y] = x;
            if (isPromising(y)) {
                go(y+1, n);
            }
        }        
        
    }
    private boolean isPromising(int y) {
        for (int i = 0; i < y; i++) {
            if (row[y] == row[i] || Math.abs(row[y] - row[i]) == Math.abs(y - i)) {
                return false;
            }
        }
        return true;
    }
}