백준 9663(N-Queen)

문제

코드

성공 코드
package com.company;

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

public class Main {
    private static int[] cols;
    private static int n;
    private static int result = 0;

    private static boolean isAbleAccess(int searchingColIdx){
        for(int i = 0; i < searchingColIdx; i++){
            if(cols[i] + ( n - i ) > cols[searchingColIdx]
                && cols[i] < cols[searchingColIdx]) return false;//같은 행
            if(cols[i] + ((n + 1) * (searchingColIdx - i)) == cols[searchingColIdx]) return false;//오른쪽 대각선
            if(cols[i] - ((n - 1) * (searchingColIdx - i)) == cols[searchingColIdx]) return false;//왼쪽 대각선
        }

        return true;
    }

    private static void dfs(int searchingColIdx) {
        if(n == searchingColIdx){
            result++;
        } else {
            for(int i = 0; i < n; i++){
                //열 기준으로 다음 열 서칭
                cols[searchingColIdx] = searchingColIdx + (n * i);
                if(isAbleAccess(searchingColIdx)){
                    dfs(searchingColIdx + 1);
                }
            }
        }
    }

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

        cols = new int[n];
        dfs(0);
        System.out.println(result);
    }
}

좋은 웹페이지 즐겨찾기