프로그래머스 문제풀이 (알고리즘) - N-Queen

들어가기 앞서

이 코드는 그닥 좋은 성능을 내는 코드가 아니기 때문에 참고 용도로만 보기 바랍니다.

n = 12 인 테스트에서 가장 많이 좋아요를 받은 

테스트 코드(백트래킹으로 해결)와 80.00ms 정도로 30 % 의 성능 차이가 납니다. ( 160.00ms <> 240.00ms )

 

백트래킹이라는 알고리즘을 사용하면 조금 더 빠르게 풀 수 있다고 하는데..

아직 해당 알고리즘을 모르기 때문에 성능이 그닥 좋지 않은 코드를 짜게 된 것 같습니다.

더 공부해야 할 필요성을 느꼈습니다.

 

2021-09-03

백트래킹을 배우고, 알고리즘을 개선했습니다. 

해당 풀이는 맨 아래에 있습니다.

 

시도

단순 깊이 우선 탐색으로 문제를 풀면 메모리나 시간을 초과할 것이라고 생각하고 다음과 같이 체스를 하나 놓을 때 마다 계산식을 추가해서 검사하기로 하였습니다.

만약 3,4 위치에 queen 을 놓았다면

x = 3

y = 4

y = x + 1

y = -x + 7

을 만족하는 자리에는 체스말을 놓을 수 없게 됩니다.

따라서 이 식을 이용해서 너비 우선 탐색을 진행하기로 했습니다.

 

class Solution {
    public int solution(int n) {
        queen = new int[n][2];
        dfs(0, n);
        return result.size();
    }

    private List<int[]> formula = new ArrayList<>();
    private int[][] queen;
    private Set<Integer> result = new HashSet<>();

    public void dfs(int d, int n) {

        if (d == n) {
            result.add(Arrays.deepHashCode(queen));
            return;
        }

        int x = d;
        for (int y=0; y<n; y++) {
            boolean next = isNext(x, y);

            if (next) {
                formula.add(new int[] {x, y, y - x, y + x});
                queen[d] = new int[]{x, y};
                dfs(d + 1, n);
                formula.remove(formula.size() - 1);
                queen[d] = null;
            }
        }
    }

    public boolean isNext(int x, int y) {
        boolean next = true;

        for (int f=0; f<formula.size(); f++) {
            boolean on = false;
            int[] formu = formula.get(f);
            if (x == formu[0] || y == formu[1] || y == x + formu[2] || y == -x + formu[3])
                on = true;

            if (on) {
                next = false;
                break;
            }
        }
        return next;
    }
}

 

개선

위 코드의 단점은 한칸 한칸 일일이 검사한다는 점입니다.

퀸을 놓은 행에는 더 이상 어떤 퀸도 놓을 수 없지만, 같은 행의 다른 열을 일일이 검사하기 때문에 비효율 적입니다.

퀸을 놓은 행에는 더 이상 어떤 퀸도 놓을 수 없다는 특징을 이용해서, 해당 줄에 하나의 퀸을 위치시킨 뒤

바로 다음 줄을 검사하는 방식으로 코드를 개선했습니다.

public class NQueen {
    public static void main(String[] args) {
        NQueen nQueen = new NQueen();
        System.out.println(nQueen.solution(8));
    }

    Stack<Integer[]> place = new Stack<>();
    Stack<Integer[]> stack = new Stack<>();
    int count = 0;

    public int solution(int n) {
        for (int i=1; i<=n; i++)
            dfs(1, i, n);

        return count;
    }

    public void dfs(int row, int column, int stop) {


        if (isNext(row, column)) {
            place.add(new Integer[]{row, column});

            if (row < stop) {
                for (int i = 1; i <= stop; i++)
                    dfs(row + 1, i, stop);
            } else
                count++;

            place.pop();
        }
    }

    public boolean isNext(int row, int column) {
        // 조건 탐색
        for (int i=0; i<place.size(); i++) {
            Integer[] old = place.get(i);

            // 열이 동일하면 or 행의 차이분 만큼 열도 차이가 날때
            if (old[1] == column || Math.abs(old[0] - row) == Math.abs(old[1] - column))
                return false;
        }
        return true;
    }
}