[JAVA] 9663. N-Queen

Queen은 대각선, 같은 행, 열에 존재하면 서로 공격할 수 있다.

즉, 서로 공격할 수 없는 퀸의 위치는 모두 각각의 위치에서 행과 열에서 만날 수 없고, 대각선 상으로도 위치하고 있지 않아야 한다.

처음에는 메모리 초과가 발생하였다. 각 위치를 비교해야하므로 이전 위치를 Node 클래스를 만들어서 list 비교를 진행했었다.

 

하지만 그럴 필요 없이 1차원 배열만으로 해결이 가능하였다. 

그 이유는 N이 주어졌을 때 N개의 퀸이 위치해야하므로 모든 행에 대해서는 무조건 퀸이 존재해야 만족한다.

따라서 우리는 열의 위치만을 생각하면 된다.

1차원 배열에서 인덱스는 행을 의미하고 행에 따른 배열의 값이 바로 열의 위치를 알려준다고 생각하면 1차원 배열로 모든 퀸의 위치를 알 수 있게 된다.

퀸의 위치는 처음부터 모든 경우를 구해야하므로 순열과 for문을 합친 구조이다.

백트래킹의 개념으로 중간에 위치가 만족되지 않으면 더이상 다음의 재귀로 넘어가지 않는다.

모두가 만족시키는 N개의 배열이 되었을 시 result의 개수를 증가시켜서 출력값을 만들어갔고, 퀸의 행과 열의 비교에서 행은 항상 그 행에 대해서 하나만을 위치시키므로 행이 같을 경우는 존재하지 않으므로 열과 대각선의 비교만을 진행하면 된다.

대각선의 비교는 각 행의 차와 각 열의 차의 절대값이 서로 같은 값을 가지면 그 위치는 서로 대각선 상에 존재함을 알 수 있다.

 

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class B_9663_NQueen {
 
    static int result;
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int[] board = new int[N]; // 퀸의 위치 - 행은 index(무조건 한 행에 한개의 퀸이 위치해야 하므로), 열이 배열의 값
        solve(0, N, board);
        System.out.println(result);
    }
 
    private static boolean isPossible(int cnt, int x, int[] board) {
        for (int i = 0; i < cnt; i++) {
            // 같은 행은 비교할 필요가 없고, 열에 존재하거나 대각선 상에 존재할 경우
            if (x == board[i] || Math.abs(cnt - i) == Math.abs(x - board[i]))
                return false;
        }
        return true;
    }
 
    private static void solve(int cnt, int N, int[] board) {
        if (cnt == N) {
            result++;
            return;
        }
        for (int i = 0; i < N; i++) {
            if (isPossible(cnt, i, board)) {
                board[cnt] = i;
                solve(cnt + 1, N, board);
            }
        }
    }
 
}