프로그래머스 Level 2 - 연습문제 - NQueen

• N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

 

---

백트래킹의 대표적인 문제 NQueen 문제입니다.

아래 블로그를 보며 공부하였습니다. 

https://st-lab.tistory.com/118

[백준] 9663번 : N-Queen - JAVA [자바]

 

1. 1차원 배열을 생성 index 는 row 값이 될 것이고 value 는 col 값이 될 것입니다.

2. nQueen 이라는 재귀함수를 만든 후 시작인덱스 0을 넣어줍니다.

3. 재귀함수의 depth == n 일 경우 ( 퀸을 모두 놓음) 시 count++ , return 할 수 있도록 기저사례를 정합니다.

4. for문을 이용하여 arr[depth (row)] = i (col) 으로 초기화 하며 Possibility 라는 함수를 만들어 체크합니다.

5. Possibility 안에서 for문을 이용하여 현재 line 의 arr[row] 값과 다음 line 의 arr[i] 가 같지 않을 때 ( 같은 열이 아닐 때 )

그리고 [ row - i ] == [ arr[row] - arr[i] ] 가 아닐 때

( 대각선의 경우 현재 열 - 행 == 구할 값 arr[열] - arr[행] 의 절대 값이 같을 때 )

false 를 반환하고 통과하면 true를 반환

 

아래는 코드입니다.

import java.util.*;


class Solution {
    
    static int n;
    static int count=0;
    static int[] arr;
    
    
    public int solution(int nq) {
        n = nq;
        arr = new int[n];
        nQueen(0);
        
        return count;
    }
    
    public static void nQueen(int 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;
    }
    
    
}