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

[프로그래머스]N-Queen

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

코딩테스트 연습 - N-Queen

풀이

순열을 사용하여 풀었다. 순열로 퀸의 순서를 뽑아준 후, 뽑은 퀸을 이전의 뽑았던 퀸의 위치와 비교하여 뽑을 수 있는 위치라면 재귀함수를 사용해 순환적으로 호출해주었고, 뽑을 수 없는 위치라면(행이 같거나 대각선 위치에 존재하거나) 퀸을 뽑지 않았다. 

 

뽑을 때는 1차원 배열을 이용해 각 인덱스가 하나의 열을 나타내도록 하였다. 

0번 인덱스는 첫 번재 열에서의 퀸 위치를 저장하도록

1번 인덱스는 두 번째 열에서의 퀸 위치를 저장하도록

... n - 1번 인덱스는 n번째 열에서의 퀸의 위치를 저장하도록 하였다.

 

행이 같은지 확인할 때에는 배열의 요소를 비교해 주었고,

대각선 위치에 존재하는지 확인하기 위해서 Math.abs()함수를 사용하였다. 두 개의 퀸의 위치가 서로 행의 차이와 열의 차이가 같다면 대각선에 존재하는 것이므로 아래와 같이 작성하였다.

Math(i - idx) == Math(pick[i] - pick[idx])

 

코드

import java.util.*;
 
class Solution {
    
    boolean[] visited;
    int[] pick; //뽑은 위치를 저장. 0번인덱스는 첫 번째 줄에서 퀸의 위치를 의미한다. 
    int count;
    
    public int solution(int n) {
        visited = new boolean[n];
        pick = new int[n];
        count = 0;
        
        permutation(n, 0);
        return count;
    }
    
    public void permutation(int n, int idx) {
        if(n == idx) {
            count++;
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                pick[idx] = i;
                if(check(idx)) permutation(n, idx + 1);
                visited[i] = false;
            }
        }
    } 
    
    public boolean check(int idx) {
        for(int i = 0; i < idx; i++) {
            if(pick[i] == pick[idx]) return false; //같은 행에 퀸이 존재하면 false
            if(Math.abs(idx - i) == Math.abs(pick[idx] - pick[i])) return false; //대각선에 퀸이 존재한다면 false
        }
        return true;
    }
}