[프로그래머스 , 자바] Level2: N-Queen

 

 

문제분석:

 

길이가 N인 보드판에  N개의 퀸말을  서로 공격할수없는 상태로 만드는 형태의 갯수를 구하는문제다.

 

이 문제를 처음 접근할때 대부분의 사람들은  2차원 배열을 만들고 완전탐색을 진행할것이다.

(본인도 2차원배열 만들어놓고 접근하니  뭔가 이상하게.. 산으로가는 느낌이 들엇다.)

 

이 방식으로 접근을 해서 푸는것도 하나의 방법이겟지만,  더 좋은 방법이 있다.

 

2차원배열을 1차원배열로 압축시켜버리는것이다.

 

어떻게 1차원 배열로 압축을 시킬까?

 

배열의 index를 행,  배열의 값을 열로 보는것이다.

예시로 들자면, 이 배열을 1차원으로 압축시키면  [1,3,0,2] 라는 값이 나온다.

 

이 압축시킨 배열로 백트래킹 기법을 사용하는것이다.

 

하지만, 퀸을 놓을수있는조건은  가로, 세로, 대각선이 겹치면 안된다.

 

여기서 우리는 가로, 대각선의 규칙만 살펴보면된다. 

세로는 1차원으로 압축시켜서 고려를 전혀 안해도된다. (압축의 이점 1)

 

게다가, 2차원배열과달리 이 방법은 퀸의 배치의 중복을 피할수가있다. (압축의 이점 2)

 

 

가로의 경우엔,  지금까지 놓여진말들의 열값이  앞으로 놓일 열값과 동등하면 안된다.(조건1)

 

대각선의 경우엔,  지금까지 놓여진말들의 행,열과 앞으로 놓일 행,열의 기울기가 동등하면 안된다.(조건2)

 

조건2의 대해 더 자세하게 이야기를하자면,  퀸의 대각선은 기울기가 1인 경우다.

기울기가 1은 즉,  x1-x2/y1-y2 =1  ,  x1-x2 = y1-y2 인 경우다.  

 

 

조건을 모두 세팅햇다면, 남은건 백트래킹 조합만 하면 완료다.

문제풀이

import java.util.*;
class Solution {      
   // 2차원 배열 문제를 1차원으로 압축
   // 배열의 index를 행, 배열의 값을 열로 잡자.
    int[] board;
    int count=0;
    
    public int solution(int n) {
 
        board= new int[n];
        backTracking(n,0);
        
        return count;
    }
    
    public void backTracking(int n,int row){
        
        if(row==n){
            count++;
            return;
        }
        
        for(int i=0;i<n;i++){
            board[row]=i;          
            if(possible(row)){
                backTracking(n,row+1);
            }
        }        
    
    }
    
    public boolean possible(int row){
        
        for(int i=0;i<row;i++){
             //가로가 같을때
            if(board[i]==board[row]){
                return false;
            }           
            //대각선 (기울기)가 같을때
            if(Math.abs(row-i)==Math.abs(board[row]-board[i])){
                return false;
            }
        }
        return true;
    }
}