(Java) 프로그래머스 - N-Queen

백트래킹을 사용해야 하는 유명한 문제이다.

어떻게 푸는지는 대강 알고 있었는데 실제로 풀어본 적이 없어서 풀어봤다.

2차원 배열 arr과 visited를 이용해서 문제를 풀어보려고 시도했는데

뭔가 코드만 복잡해지고 생각한 것처럼 구현이 되지 않았다.

1시간을 시도하다가 검색하니 2차원 배열을 1차원 배열로 압축해서 풀이가 있어

간단하게 풀었다.

 

2차원 배열을 이용해도 풀 수 있을 것 같은데 다시 풀어봐야겠다.

 

---

최종 코드

class Solution {
    static int[] arr;
    static int cnt;
    public int solution(int n) {
        int answer = 0;
        // 2차원 배열을 1차원으로 압축 -> 인덱스를 행, 값을 열로 보는것
        arr = new int[n];

        // BackTracking 호출
        bt(n ,0);

        answer = cnt;
        return answer;
    }
        // BackTracking 메서드
    static void bt(int n, int row) {
        // 모든 queen이 다 놓였다면
        if(n == row) {
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            arr[row] = i;
            // 리턴값이 true이면 BackTracking
            if(check(row)) {
                bt(n ,row + 1);
            }
        }
    }

    // 가로, 세로, 대각선 확인 메서드
    static boolean check(int row) {
        for (int i = 0; i < row; i++) {
            // 가로, 세로 확인
            if(arr[i] == arr[row]) {
                return false;
            }

            // 대각선 확인 (두 점의 기울기가 같으면 대각선에 위치한 것)
            if(Math.abs(row - i) == Math.abs(arr[row] - arr[i])) {
                return false;
            }
        }
        return true;
    }
}