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

이 문제는 완전 탐색을 이용해서 풀었다.

 

처음에는 정말 온전히 완전 탐색을 이용해서 구현했다. 하지만 정답은 나오나 시간 초과가 떴다.

조금만 생각해보면 시간을 완전히 줄일 수 있다.

 

N * N 체스판에 N개의 퀸을 놓는다. 퀸은 가로, 세로, 대각선 전체를 이동할 수 있기 때문에, N * N 체스판에 N개의 퀸을 놓으려면 모든 행에 하나씩 퀸이 있는 모습일 것이다. 이 점을 이용하면 시간을 굉장히 많이 줄일 수 있다.

class Solution {
    
    int N;
    int[][] board;
    
    int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
    int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
    
    public int solution(int n) {
        N = n;
        board = new int[n][n];
        
        final int answer = solve(0, 0);
        
        return answer;
    }
    
    int solve(final int y, final int cnt) {
        if (y == N) {
            return 1;
        }
        
        int result = 0;
        for (int x = 0; x < N; x++) {
            if (board[y][x] == 0) {
                set(y, x, 1);
                result += solve(y + 1, cnt + 1);
                set(y, x, -1);
            }
        }
        
        return result;
    }
    
    void set(final int y, final int x, final int to) {
        board[y][x] += to;
        
        for (int i = 0; i < 8; i++) {
            Pair present = new Pair(y, x);
            
            while (true) {
                final int distY = dy[i];
                final int distX = dx[i];
                
                Pair next = nextPos(present.y, present.x, distY, distX);
                
                if (next.y == -1) {
                    break;
                }
                
                board[next.y][next.x] += to;
                present = next;
            }
        }
    }
    
    Pair nextPos(final int y, final int x, final int distY, final int distX) {
        final int ny = y + distY;
        final int nx = x + distX;
        
        if (inRange(ny, nx)) {
            return new Pair(ny, nx);
        }
        return new Pair(-1, -1);
    }
    
    boolean inRange(final int y, final int x) {
        if (0 <= y && y < N && 0 <= x && x < N) {
            return true;
        }
        return false;
    }
    
    static class Pair {
        int y;
        int x;
        
        Pair(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}