[JAVA] 프로그래머스 LEVEL2 N-Queen

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

프로그래머스

코딩테스트 연습 > 연습문제 > N-Queen

 

난이도: LEVEL2

알고리즘 유형: 백트래킹

문제 접근 

방문 체크용 배열을 3개 만든다. 

1. 왼쪽 아래 → 오른쪽 위 대각선 배열 

2. 왼쪽 위  → 오른쪽 아래 대각선 배열

3. 세로 배열 

 

1번 배열 

 

2번 배열

 

방문 체크를 x,y 좌표를 통해서 한다. 

왼쪽 아래에서 오른쪽 위 방향의 대각선은 x+y

왼쪽 위 오른쪽 아래 방향의 대각선은 x-y+n(init 값)

정답 코드 

class Solution {
    static int answer = 0;
    static boolean [] arr1; // 왼쪽 아래 -> 오른쪽 위 대각선
    static boolean [] arr2; // 왼쪽 위 -> 오른쪽 아래 대각선
    static boolean [] arr3; // 세로 
    static int N;
    public int solution(int n) {
        arr1 = new boolean [n * 2];
        arr2 = new boolean [n * 2];
        arr3 = new boolean [n];
        N = n;
        bt(0);
        return answer;
    }
    public static void bt(int x){
        if(x == N){
            answer++;
            return;
        }
        for(int y = 0; y < N; y++){
            if(arr1[x + y] || arr2[x - y + N] || arr3[y]) continue;
            arr1[x + y] = true;
            arr2[x - y + N] = true;
            arr3[y] = true;
            bt(x + 1);
            arr1[x + y] = false;
            arr2[x - y + N] = false;
            arr3[y] = false;
        }
    }
}