[프로그래머스 Level.2] N-Queen (연습문제) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 연습문제 > N-Queen

 

 

문제 설명

 

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

 

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

 

 

 

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

 

제한사항

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

 

---

 

입출력 예

n	result
4	2

입출력 예 설명

 

입출력 예 #1
문제의 예시와 같습니다.

 

 

나의 코드

class Solution {
    
    int[] arr;
    int answer;
    public int solution(int n) {
        answer = 0;
        
        arr = new int[n];
        
        dfs(0, n);
        
        return answer;
    }
    
    public void dfs(int depth, int n) {
        if(depth == n) {
            answer++;
            return;
        }
        
        for(int i=0; i<n; i++) {
            arr[depth] = i;
            
            if(check(depth)) {
                dfs(depth+1, n);
            }
        }
    }
    
    public boolean check(int depth) {
        for(int i=0; i<depth; i++) {
            // 같은 행에 놓일경우
            if(arr[depth] == arr[i]) { 
                return false;
            }
            
            // 대각선에 놓일 경우 (열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우)
            if(Math.abs(arr[depth]-arr[i]) == Math.abs(depth-i)) { 
                return false;
            }
        }
        
        return true;
    }
    
}

 

풀이

1. 완전탐색 dfs를 이용해서 n개의 퀸을 배치할 수 있는 총 경우의 수를 찾으면 된다.
2. 2차원 배열로 푸는 방법보다는 1차원 배열로 index를 열로, 값을 행으로 생각하고 풀면 된다.
3. 같은 행에 놓는 경우와 대각선에 놓는 경우를 판별해서 제외하고 재귀 호출해서 풀어야 한다.