[프로그래머스], [백준 9663 번] N-Queen - 백트래킹

문제

---

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

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

		Q
Q
			Q
	Q

	Q
			Q
Q
		Q

 

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

 

 

[제한사항]

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

 

 

 

 

풀이

---

DFS 방식으로 하나씩 대입하여 가능한 경우수를 판단하면 된다.

여기서 한개의 행에는 하나의 퀸만 있을 수 있다는 점을 생각하면 경우의 수를 줄일 수 있다.

 

for(int i = 1 ; i <= n ; i++){
    col[1] = i;

    dfs(col, n, 1);
}

위와 같은 방식으로 첫번째 행의 퀸 위치를 정해준 뒤 깊이 우선 탐색을 한다.

 

static void dfs(int[] col, int n, int row){

    if(row == n){
        count++;
        return;
    }

    for(int i = 1; i <= n ; i++){
        col[row + 1] = i;
        if(isPossible(col, row + 1)){
            dfs(col, n, row + 1);
        }
    }        
}

깊이 우선 탐색을 하면서 가능한 경우라면 더 깊이 들어가면 된다.

 

퀸이 들어 갈 수 있는 위치는 전에 있던 것들과 같은 열 또는 대각선이 아니면 된다.

대각선이 아닌지 확인 하기 위해서

 

위 그림과 같이 row - i  와 col[i] - col[row] 의 절대 값이 같다면 대각선이다.

 

<전체방향>

class Solution {
    
    static int count;
    public int solution(int n) {
        int answer = 0;
        
        int[] col = new int[n + 1];
        for(int i = 1 ; i <= n ; i++){
            col[1] = i;

            dfs(col, n, 1);
        }
        
        answer = count;
        return answer;
    }
    
    static void dfs(int[] col, int n, int row){

        if(row == n){
            count++;
            return;
        }

        for(int i = 1; i <= n ; i++){
            col[row + 1] = i;
            if(isPossible(col, row + 1)){
                dfs(col, n, row + 1);
            }
        }        
    }
    
    
    static boolean isPossible(int[] col, int row){
        
        for(int i = 1; i < row; i++){
            if(col[i] == col[row]){
                return false;
            }
            
            if(Math.abs(i - row) == Math.abs(col[i] - col[row])){
                return false;
            }
        }
        
        return true;
    }
}