21.09.07 기록

백준 알고리즘 9663 풀이

🎆해설(메모리 14.5MB, 시간 5.5s로 통과)

-백트래킹을 쓰는 건 알겠는데 코드로는 어떻게 구현해야할지 잘 모르겠어서 그냥 해설을 봤다.
-2차원 boolean[] 배열로 풀이를 시도했었는데, 해설은 1차원 배열을 사용했다.
-지난 백트래킹 문제와 비교했을 때 로직은 크게 다르지 않은데.. 왜 생각을 못했을까 싶다.😂

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B9663 {
    public static int N;
    public static int[] chess;
    public static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        chess = new int[N];

        nQueen(0);
        System.out.println(cnt);
    }

    public static void nQueen(int depth) {
        if(depth == N) {
            cnt++;
            return;
        }

        for(int i = 0; i < N; i++) {
           chess[depth] = i;

           if(isPossible(depth)) {
               nQueen(depth+1);
           }
        }
    }

    public static boolean isPossible(int col) {
        for(int i = 0; i < col; i++) {
            if(chess[col] == chess[i]) {
                return false;
            }

            //행과 열의 차가 같다면 대각선에 놓여있는 경우다.
            else if (Math.abs(col - i) == Math.abs(chess[col] - chess[i])) {
                return false;
            }
        }
        return true;
    }
}