프로그래머스 Lv3 N-Queen

문제풀이

 N개의 퀸을 하나씩 가능한 자리에 놓는 dfs 문제이다.

 1. N*N 체스판에 N개의 퀸을 놓으므로 한 열에 퀸을 하나씩 놓으면 된다.

 2. answer를 static 변수로 선언해 둔다.

 3. depth가 i 일 때, i번째 열의 퀸의 위치를 결정하며, depth를 1씩 증가시켜간다.

 3-1. i번째 열의 퀸의 위치를 결정할 때는 j<i인 j 열의 퀸들의 위치를 참고한다. i번째 퀸과 j번째 퀸의 행이 같으면 안되며 대각선에 있어도 안된다.(row_i - row_j != col_i - col_j)

 4. depth가 N이 되면 2에서 선언한 answer에 1을 더해준다.

 5. 가능한 모든 경우에 대하여 3 ~ 4 를 반복한 후 answer를 반환한다.

 

Java Code

class Solution {
    static int answer = 0;
    static int combi = 0;
    public int solution(int n) {
        int[] coord = new int[n];
        
        for(int i=0; i<n ; i++) {
            coord[0] = i;
            explore(coord, 1 , n);
        }
        
        return answer;
    }
    
    public void explore(int[] coord, int depth, int n) {
        if(depth==n) {
            answer+=1;
            return ;
        }
        for(int i = 0 ; i < n ; i++) {
            coord[depth] = i ;
            if(check(coord, depth)) {
                explore(coord, depth+1 , n);
            }
        }
    }
    
    public boolean check(int[] coord, int depth) {
        for(int i = 0 ; i< depth ; i++) {
            if(!checkPair(coord,i,depth)) {
                return false;
            }
        }
        return true;
    }
    public boolean checkPair(int[] coord, int i, int j) {
        if(coord[i]==coord[j]) {
            return false;
        }else if(Math.abs(i-j)==Math.abs(coord[i]-coord[j])) {
            return false;
        }else {
            return true;
        }
    }
}

Line 4 의 solution method가 main method로, 첫번째 열의 퀸의 위치를 결정한 후 dfs(explore method)를 호출한다.

Line 15 의 explore method가 dfs를 실행하는 부분으로, depth가 n이 되면 answer에 1을 더해주며, depth가 n보다 작은 경우에는 depth 열의 퀸의 위치를 결정한다. depth 열의 퀸의 가능한 모든 위치에 대하여 depth+1로 다시 explore method를 호출한다.

Line 28의 check method와 line 36의 checkPair method로 과정 3-1의 조건을 구현한다. checkPair는 두 개의 퀸의 위치를 비교하며, check에서 마지막 퀸의 위치와 이전 퀸들의 위치를 비교한다. 이전 퀸들 간의 위치는 이전 depth에서 고려했을 것이므로 다시 할 필요는 없다.

 

문제 링크

프로그래머스