Nqueen 실행시간을 더 줄이고 싶은데, 방법이 없나요?

  • kingik
    kingik

    java로 작성하였습니다.

    줄마다 Nqueen의 조건을 만족하는 위치를 모두 찾아서 그 위치들에 한

    해서만 재귀함수를 호출하도록 하였습니다. 예를 들어 10-10 체스판에

    서 4번째 행까지는 queen의 위치가 각 행마다 고정되어 있는 상태에서

    5번째 행에서 기존에 배치되어 있는 4개의 queen과 서로 공격하지 못

    하는 위치를 2개를 찾았을 때, 1번 위치를 지정하고 바로 다음 행

    로 넘어가 가능한 위치를 찾거나, 1번위치를 건너뛰고 2번 위치를 지

    정하고 다음 행으로 넘어가는 등의 방식으로 최대한 시간을 줄여보았

    는데, 결과가 만족스럽지 않아서요.. 더 줄이는 방법 아시는 분 있으

    면 답변 부탁드려요 ㅠ

    import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int lines = Integer.parseInt(sc.nextLine());
        int[] result = new int[lines];
        for(int i=0; i<lines; i++){
            int n = Integer.parseInt(sc.nextLine());
            result[i] =select(0, 0, new int[n], n);
        }
        for(int r: result){
            System.out.println(r);
        }
        sc.close();
    }

    public static int select(int r, int c, int[] sel, int n){
        if(r == n-1){
            int num=0;
            for(int i=0; i<n; i++){
                if(check(r, i, sel)) num+=1;
            }
            return num;
        }
        int[] csel = Arrays.copyOf(sel, n);
        csel[r] = c;
        int nextc =0;
        for(int j=c+1; j<n; j++){
            if(check(r, j, sel)) {
                nextc = j;
                break;
            }
        }
        if( nextc !=0) {
            if(!check(r, c, sel)) return select(r, nextc, sel, n);
            return select(r+1, 0, csel, n)+select(r, nextc, sel, n);
        }
        else{
            if(!check(r, c, sel)) return 0;
            return select(r+1, 0, csel, n);
        }
    }

    public static boolean check(int r, int c, int[] check){
        for(int i=0; i<r; i++){
            if(c == check[i]) return false;
            else if(Math.abs(r-i) == Math.abs(c-check[i])) return false;

        }
        return true;
    }
}

    7년 전
2개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    check 함수 대신 배열들을 통해 세로와 대각선을 이용한 판정 여부를 체크하게 하면 수행시간 개선을 보실 수 있습니다. 예컨데 column 라는 배열을 만들고 column[c] = true 일 경우 c번째 열에 이미 말이 놓여있음을 알 수 있으니 해당 위치에 포함할 수 있는지를 한번의 참조를 통해 알 수 있습니다. 그리고 대각선의 경우 힌트를 드리자면, 체스판에 대해 각 칸에 대응하는 행번호와 열번호의 합을 각 칸에 넣어보시면 규칙성이 있다는 사실을 아실 수 있습니다.


    7년 전 link
  • kingik
    kingik

    감사합니다~


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.