[백준] 9963번 N-Queen

단계별로 풀어보기 백트래킹의 5단계 문제

그 유명한 N-Queens Problem이다.

9663번: N-Queen

이번학기 알고리즘 시간에 정말 잘 배운 문제라 쉽게 풀 수 있었다.

import java.util.Scanner;

public class Main {
    static int count = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] col = new int[n];
        queen(col, n, 0);
        System.out.println(count);
    }

    static void queen(int[] col, int n, int num) {
        if (num == n) {
            count++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (promising(col, num, i)) {
                 col[num] = i;
                 queen(col, n, num + 1);
                 col[num] = 0;
            }
        }
    }
    static boolean promising(int[] col, int r, int c) {
        for (int i = 0; i < r; i++) {
            if(col[i] == c || Math.abs(c - col[i]) == Math.abs(r - i)) {
                return false;
            }
        }
        return true;
    }
}