[백준] 9663번 : N-Queen

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

문제

 

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

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

 

입력

 

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

 

출력

 

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

 

 

풀이 방법

 

퀸은 일직선이나 대각선으로 모두 공격이 가능하다.

배열에서 판별하려면 행과 열의 범위 조정을 통해 판별이 가능한데

배열의 인덱스를 행으로, 배열의 값을 열로 설정하여 작성이 가능하다.

 

만약 다른 행에 대해서 같은 값을 가지면 우로 만나는 경우가 되고

대각선의 경우에는 행의 차와 열의 차가 같은 경우가 되므로

위의 두 경우를 제외하여 문제를 풀면 된다.

 

작성 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;   public class Main {       static int N;     static int arr[];     static int count=0;       public static void main(String[] args) throws IOException {           BufferedReader br=new BufferedReader(new InputStreamReader(System.in));           N=Integer.parseInt(br.readLine());         arr=new int[N]; // 행에 들어갈 좌표           nQueen(0);         System.out.println(count);     }       public static void nQueen(int index) {           if(index==N){             count++;             return;         }           for(int i=0;i<N;i++){             arr[index]=i;             if(possibility(index)){                 nQueen(index+1);             }         }     }       public static boolean possibility(int index) {           for(int i=0;i<index;i++){             if(arr[index]==arr[i]){ // 다른 행에 대해서 같은 값을 가지면 우로 만난다.                 return false;             }             else if(Math.abs(arr[index]-arr[i])==Math.abs(index-i)){ // 대각선의 경우 : 행의 차 = 열의 차                 return false;             }         }         return true;     } }