[프로그래머스] NQueen

문제 설명

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

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

 

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

제한사항

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

---

입출력 예nresult

4

2

입출력 예 설명

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

 

문제 풀이

조건을 보면,

1. 체스판의 가로, 세로 길이 및 퀸 개 수는 N개 이다.

2. N은 최대 12개

3. 대각선, 가로, 세로에 퀸이 겹치지 않아야함 이다.

 

가로, 세로가 겹치지 않으려면 각 퀸 끼리 x 좌표, y좌표가 겹치지 않아야 함.

** 대각선이 겹치지 않으려면  이미 놓아진 체스말과의 밑변, 높이가 같지 않아야 한다.

즉 아래 소스에서 level (행)의 경우 항상 level이 높기에 level - 이전 체스 말의 x좌표 != (현재 체스말의 열의 위치 - 이전 체스말의 열의위치의 절대 값) 이 같지 않아야한다.

 

최종적으로 각 행을 모두 완성하면 완료

 

private int N;
private int answer;
private int[] queenPosition;

public int solution(int n) {
    this.N = n;
    queenPosition = new int[N];
    dfs(0);
    return answer;
}
public void dfs(int level) {
    if (level == N) {
        answer++;
    } else {
        for (int i = 0; i < N; i++) {
            queenPosition[level] = i;
            if (validation(level)) {
                dfs(level + 1);
            }
        }
    }
}
public boolean validation(int level) {
    for (int i = 0; i < level; i++) {
        if (queenPosition[i] == queenPosition[level]
                || level - i == Math.abs(queenPosition[level] - queenPosition[i])) {
            return false;
        }
    }
    return true;
}