programmers_N-Queen_java

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

프로그래머스

 

두 점 사이 기울기 == 1 -> (x1 - x2) == (y1 - y2)  -> 대각선 상에 위치

class Solution {

    private static int count;
    
    public static int solution(int n) {
        int answer = 0;
        count = 0;
        dfs(n, 0, new int[n]);
        answer = count;
        return answer;
    }

    public static void dfs(int n, int col, int[] visited){
        if(col == n){
            count++;
            return;
        }

        for (int i = 0; i<n; i++){
            visited[col] = i;
            if (isPossible(col, visited)){
                dfs(n, col+1, visited);
            }
        }
    }

    public static boolean isPossible(int col, int[] visited){
        for (int i = 0; i< col; i++){
            if (visited[col] == visited[i]){ // 같은 열에 퀸이 배치되어 있는 경우
                return false;
            }
            if (Math.abs(col-i) == Math.abs(visited[col] - visited[i])){ // 대각선상 퀸이 배치되어 있는 경우(두 점 사이 기울기== 1)
                return false;
            }
        }
        return true;
    }
    
   
}