프로그래머스 [Lv. 2] N-Queen {언어 : Java} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12952?language=java

프로그래머스

정답 코드

class Solution {
    private int n;
    private boolean[] cols;
    private boolean[] diag1;
    private boolean[] diag2;

    private int nqueen(int x) {
        if (x == n) {
            return 1;
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!cols[i] && !diag1[x + i] && !diag2[x - i + n - 1]) {
                cols[i] = diag1[x + i] = diag2[x - i + n - 1] = true;
                cnt += nqueen(x + 1);
                cols[i] = diag1[x + i] = diag2[x - i + n - 1] = false;
            }
        }
        return cnt;
    }

    public int solution(int n) {
        this.n = n;
        cols = new boolean[n];
        diag1 = new boolean[2 * n - 1];
        diag2 = new boolean[2 * n - 1];

        return nqueen(0);
    }
}

풀이 방법

 

1. 열, 대각선 사용 여부 확인: 각 열과 대각선을 사용했는지 여부를 저장하여 퀸을 놓을 때마다 확인한다. 이렇게 하면, 각 단계에서 모든 이전 퀸들과의 비교를 피하고, O(1) 시간 안에 충돌 여부를 확인할 수 있다.
2. cols, diag1, diag2 배열 사용:
   1. cols[i]: i번째 열에 퀸이 있는지 여부를 저장한다.
   2. diag1[i]: / 방향 대각선에 퀸이 있는지 여부를 저장한다. diag1은 row+col 값이 동일한 위치의 모든 셀을 포함한다.
   3. diag2[i]: \ 방향 대각선에 퀸이 있는지 여부를 저장한다. diag2는 row-col+n-1 값이 동일한 위치의 모든 셀을 포함한다.

 

느낀점

• 지난 n-queen의 속도보다 더 빠른 방법을 지피티를 통해서 알아봤다.
• 효율은 거의 100배 이상 빠르다.