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

프로그래머스

 

풀이

 

1. 아이디어

• 2차원배열을 1차원으로 축소해서 배열의 인덱스 = x좌표, 배열의 값 = y 좌표로 만들었다.
• 대각선에 위치해있으면 안된다. 즉, A퀸과 B퀸의 기울기의 절댓값이 1이면 안됨.
  • 기울기 구하는 공식 = (X2 - X1) / (Y2 - Y1)
• 즉, |X2 - X1| == |Y2 - Y1| 일 경우 대각선에 위치한 경우
• 0~n의 위치에 배치한 뒤에, 이전까지 배치한 퀸들과 비교해주면서 놓을 수 있는지 확인

2. 백트래킹

 

백트래킹은 해를 끝까지 구하기 전에, 불가능 할 경우 부모 노드로 돌아가서 다시 해를 구하는 방법이다.

가지치기라고 이해하면 편하다.

 

3. 1차원으로 축소한 이유

처음에는 2차원으로 진행하려고 했는데, 힌트를 보고 1차원으로 구현했다.

1차원으로 축소해도 되는 이유 중 하나는, 퀸은 가로·세로·대각선으로 다 갈 수 있기 때문에 한 열에 하나의 퀸만이 위치할 수 있기 때문이다. (그래서 x좌표를 인덱스로 사용하는 이유)

 

전체코드

import java.io.*;
import java.util.*;

//2차원을 1차원으로 축소해서 해결할 것!
class Solution {
    static int map[];
    static int count;
    public int solution(int n) {
        map = new int[n];
        Col(0, n);
        
        return count;
    }
    static boolean Valid(int x){
        for(int i=0; i < x; i++){
            if(map[x] == map[i]){
                return false;
            }
            if(Math.abs(x-i) == Math.abs(map[x] - map[i])){
                return false;
            }
        }
        return true;
    }
    static void Col(int depth, int n){
        if(depth == n){
            count++;
            return;
        }
        for(int i=0; i<n; i++){
            map[depth] = i;
            if(Valid(depth)){
                Col(depth+1, n);
            }
        }
    }
}