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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력

8

예제 출력

92

풀이

백트레킹으로 푸는 문제이다. 첫번째 행에 퀸을 놓고 두번째 줄로 내려간다. 두번째 줄 가능한 자리에 놓고 세번째 자리로 내려간다. 그러다 안되는 경우가 발생하면 다시 두번째 줄로 올라가 그 다음 가능한 자리로 가서 확인을 한다.

퀸의 같은 경우 같은 행이나 열에 있으면 서로 공격이 가능하므로 1차원 배열을 사용해서 같은 행에 존재하는 경우를 배제한다.

boards[x]=y의 의미는 (x+1)행의 (y+1)열에 퀸이 존재한다는 의미이다.

구현

python
pypy로 제출해야 통과한다.

n=int(input())
boards=[0]*n
ans=0
def check(x):
    for i in range(x) :
        if boards[x]==boards[i] :
            return False
        elif abs(boards[x]-boards[i])==abs : # 같은 열에 존재하는지 확인
            return False
    return True
def dfs(x):
    global ans
    if x==n :
        ans+=1
        return
    else :
        for i in range(n) :
            boards[x]=i
            if check(x)==True:
                dfs(x+1)

dfs(0)
print(ans)

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BOJ_9663 {
    static int n;
    static int ans;
    static List<Integer> boards=new ArrayList<>();

    public static boolean check(int x){
        for(int i=0; i<x; i++){
            if(boards.get(x) == boards.get(i)){
                return false;
            }else if(Math.abs(boards.get(x) - boards.get(i))==x-i){
                return false;
            }
        }
        return true;
    }
    public static void dfs(int x){
        if(x==n){
            ans+=1;
            return;
        }
        for(int i=0; i<n; i++){
            boards.set(x, i);
            if(check(x)==true){
                dfs(x+1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i=0; i<n; i++){
            boards.add(0);
        }
        ans=0;
        dfs(0);
        System.out.println(ans);
    }
}