[백준] Java, C++ N-Queen (9663)

문제

www.acmicpc.net/problem/9663

9663번: N-Queen

 

풀이

C++

#include <iostream>
using namespace std;
bool a[15][15];
int n;
bool check_col[15];
bool check_dig[40];
bool check_dig2[40];
bool check(int row, int col) {
    if (check_col[col]) {
        return false;
    }

    if (check_dig[row+col]) {
        return false;
    }

    if (check_dig2[row-col+n]) {
        return false;
    }
    return true;
}
int calc(int row) {
    if (row == n) {
        return 1;
    }
    int cnt = 0;
    for (int col=0; col<n; col++) {
        if (check(row, col)) {
            check_dig[row+col] = true;
            check_dig2[row-col+n] = true;
            check_col[col] = true;
          
            cnt += calc(row+1);
            check_dig[row+col] = false;
            check_dig2[row-col+n] = false;
            check_col[col] = false;
  
        }
    }
    return cnt;
}
int main() {
    cin >> n;
    cout << calc(0) << '\n';
    return 0;
}

 

 

 

JAVA

import java.util.Scanner;

public class Main {

 

static int path[] = new int[16];

static int n;

static int ans;

 

public static void main(String[] args) {

 

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

 

for(int i=0; i<n; i++){

path[0] = i;

nQueen(i,0);

}

System.out.println(ans);

}

private static void nQueen(int x, int y) {

for(int i=0;i<y;i++){

        if(path[i]==x || Math.abs(x-path[i])==y-i)

        return;

    }

    if(y==n-1){

        ans++;

        return;

    }

    for(int i=0;i<n;i++){

        path[y+1]=i;

        nQueen(i,y+1);

    }

}

}