[Java] 9663. N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 

8

예제 출력 1 

92

 

---

 

 

 

🙂 다른 사람 풀이

// https://st-lab.tistory.com/118
import java.util.*;

class Main {
    public static int[] arr;
    public static int N;
    public static int count=0;

    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        N=in.nextInt();
        arr=new int[N];     // 인덱스=열, 값=행

        nQueen(0);
        System.out.println(count);
    }

    public static void nQueen(int depth){    // depth=열
        if(depth == N){
            count++;
            return;
        }

        for(int i=0; i<N; i++){         // 행
            arr[depth]=i;
            if(possibility(depth)){     // 대각선 체크
                nQueen(depth+1);
            }
        }
    }

    public static boolean possibility(int col){
        for(int i=0; i<col; i++){
            if(arr[col] == arr[i]){ // 같은 행에 퀸
                return false;
            }
            // 열의 차와 행의 차가 같으면 대각선
            else if(Math.abs(col-i) == Math.abs(arr[col]-arr[i])){
                return false;
            }
        }
        return true;
    }
}

소스 코드는 이해하기 어려운 부분이 없지만, 이 아이디어를 떠올리는 게 어려운 듯🥲

2차원 배열을 쓸 필요가 없다. 

사이즈가 n인 1차원 배열 arr을 만들고, 인덱스=열, 값=행으로 생각한다.

퀸을 둘때  같은 행과 열, 대각선을 피해야 한다.

possibility 메소드는 이미 있는 퀸들과 행, 대각선이 겹치는지 본다.

대각선은 열의 차와 행의 차가 같으면 대각선에 있는 것으로 생각한다.

파이썬 풀이도 찾아봤었는데 시간 초과가 잘 뜬다고 했다.

그냥 난 백트래킹 같은 문제는 자바로 풀어야지👻

 

 

문제 출처 👉 백준

 

 

👇 참고

https://www.youtube.com/watch?v=gcuZ_VGIcn4