[프로그래머스 - Java] N-Queen

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

 

풀이

이 문제는 n*n크기의 체스판에 n개의 퀸을 서로 한번에 공격할 수 없도록 놓는 경우의 수를 구하는 문제입니다.

n이 12이하로 매우 작은 값이기 때문에 저는 재귀를 이용하는 백트래킹 알고리즘을 사용해서 문제를 해결하였습니다.

 

우선 알아둘 것은 체스에서 퀸이 이동하는 방향은 가로, 세로, 대각선 입니다.

 

따라서 저는 맨위 가로줄 부터 한 줄에 하나씩 퀸을 하나씩 추가하면서 이미 추가되어 있는 퀸과 가로, 세로, 대각선으로 만나는 지 여부를 확인해주면서 문제를 해결했습니다.

이 때 가로줄에 하나씩 퀸을 추가하기 때문에 세로와 대각선만을 비교하였습니다.

 

<세로로 만나는 퀸이 있는지 확인>

이 경우는 그냥 새로운 퀸의 위치의 y좌표와 이미 저장된 퀸들의 y좌표 중 같은 값이 존재하는지 여부를 확인하면 됩니다.

존재하는 경우, 해당 노드는 답이 될 수 없기 때문에 이에 대한 탐색을 더이상 진행하지 않습니다.

 

<대각선으로 만나는 퀸이 있는지 확인>

대각선으로 만나는 경우의 특징을 생각해보아야합니다.

만약 좌표라고 생각한다면, 두 퀸을 연결한 선의 기울기가 1 또는 -1이 되는 경우에 대각선으로 만나게 된다는 것을 쉽게 알 수 있습니다.

그렇기 때문에 기울기를 이용하여 대각선임을 확인합니다.

따라서 |qX-X| == |qY-Y| 인 경우 대각선에 위치하게 되는 것입니다.

이 경우 역시 해당 노드는 답이 될 수 없기 때문에 이에 대한 탐색을 더이상 진행하지 않습니다.

 

import java.util.*;

class Solution {
    int answer = 0;
    
    public void queen(int[] qX, int[] qY, int cnt, int n){
        
        if(cnt == n){
            answer++;
            return;
        }
        for(int i=0; i<n; i++){
            int newX = cnt;
            int newY = i;
            int can = 1;
            
            for(int j=0; j<cnt; j++){
                int befX = qX[j];
                int befY = qY[j];
                
                //같은 세로줄에 이미 퀸이 있는 경우
                if(befY == newY){
                    can = 0;
                    break;
                }
                
                //대각선에 이미 퀸이 있는 경우
                if( ((newX-befX) == (newY-befY)) || ((newX-befX) == -(newY-befY)) ){
                    can = 0;
                    break;
                }
            }
            
            if(can == 1){
                qX[cnt] = newX;
                qY[cnt] = newY;
                queen(qX, qY, cnt+1, n);
            }
        }
    }
    
    public int solution(int n) {
        
        int[] qX = new int[n];
        int[] qY = new int[n];
        
        for(int i=0; i<n; i++){
            qX[0] = 0;
            qY[0] = i;
            queen(qX, qY, 1, n);
        }
        
        return answer;
    }
}