[알고스팟, 백준 9663] N-Queen

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • NQUEEN
  • 1000ms
  • 65536kb
  • 3345
  • 1693 (50%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

N-Queen 퍼즐은 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 퍼즐이다. (퀸은 체스에서 가장 강력한 기물로, 자신의 위치에서 상하좌우, 그리고 대각선 8방향으로 이어진 직선 상의 어떤 기물도 공격할 수 있다)

예를 들어, 맨 위의 그림은 8x8 크기의 체스판에 8개의 퀸을 서로 공격할 수 없도록 올려놓은 예를 보인다.

체스판의 크기 N 이 주어졌을 때, N-Queen 퍼즐의 답이 모두 몇 개나 되는지를 계산하는 프로그램을 작성하시오. 한 답은 N개 퀸 모두의 위치로 정의되며, 한 퀸의 위치만 다르더라도 다른 답이라고 가정한다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 C 가 주어지며, 그 이후 한 줄에 하나씩 테스트 케이스로 체스판의 크기 N (1 <= N <= 12) 이 주어진다.

출력

각 테스트 케이스마다 한 줄의 답을 출력하며, 주어진 보드 크기에 대해 N-Queen 문제의 답을 출력한다.

예제 입력

3
1
2
8

예제 출력

1
0
92

노트

---

이 문제를 풀면서 다시한번 생각해본 Deep Copy, Swallow Copy

1차원 배열일 때만 생각했었는데

2차원 배열에는 적용되지 않드라...ㅎ;;;

http://vivi-world.tistory.com/entry/JAVA-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-Deep-copy-swallow-Copy?category=679679

이걸 어떻게 풀까 하다가 재귀를 썼다.

역시 재귀는 머리가 빠질꺼같다

JAVA 1  >> 시간초과

package algoSpot.NQueen;

/**
 * Created by eunbi on 2017-12-04.
 */
public class NQueen {
    public static int sum=0;

    public static void main(String[] args) throws Exception {
        int N = 8;
        String[][] board = new String[N][N];
        initBoard(board, N);
        checkPoint(board,N,0);
        System.out.println("Total : "+sum);

    }
    public static void checkPoint(String[][] board, int n, int x){
        if(x==n){
            printBoard(board,n);
            sum++;
        }else {
            for (int y = 0; y < n; y++) {
                if (board[x][y].equals("0")) {
                    String[][] newBoard = deepCopy(board, n);
                    remove(newBoard, n, x, y);
                    checkPoint(newBoard, n, x + 1);
                }

            }
        }
    }
    public static void remove(String[][] board,int n,int x, int y){
        //1. col remove
        for(int i=0;i<n;i++){
            board[x][i] = "x";
        }
        for(int i=0;i<n;i++){
            board[i][y] = "x";
        }
        //2. / remove
        int tempY = y;
        int tempX = x;
        while( tempX>=0 &&  tempY>=0 && tempY<n && tempX<n){
            board[tempX][tempY] = "x";
            tempY++;
            tempX--;
        }
        tempY = y;
        tempX = x;
        while( tempX>=0 &&  tempY>=0 && tempY<n && tempX<n){
            board[tempX][tempY] = "x";
            tempY--;
            tempX++;
        }

        //2. \ remove
        tempY = y;
        tempX = x;
        while( tempX>=0 &&  tempY>=0 && tempY<n && tempX<n){
            board[tempX][tempY] = "x";
            tempY++;
            tempX++;
        }
        tempY = y;
        tempX = x;
        while( tempX>=0 &&  tempY>=0 && tempY<n && tempX<n){
            board[tempX][tempY] = "x";
            tempY--;
            tempX--;
        }
        board[x][y] = "Q";


    }
    public static String printBoard(String[][] board, int n){
        StringBuilder sb = new StringBuilder();
        sb.append("==========================\n");
        for(int x=0;x<n;x++){
            for(int y = 0; y < n; y++) {
                sb.append(board[x][y]+" ");

            }

            sb.append("\n");
        }
        sb.append("==========================\n");
        System.out.println(sb.toString());
        return sb.toString();
    }
    public static void initBoard(String[][] board, int n){
        for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                board[x][y] = "0";
            }
        }

    }
    public static String[][] deepCopy(String[][] original, int n) {
        if (original == null) {
            return null;
        }

        String[][] result = new String[n][n];
        for (int i = 0; i < original.length; i++) {
            System.arraycopy(original[i], 0, result[i], 0, original[i].length);
        }
        return result;
    }
}

시간초과 어케 해결하징 히히

JAVA 2  >> 백트래킹 시간초과

public static void main(String[] args) throws Exception {
    java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));

    int num = Integer.parseInt(br.readLine());
    for(;num>0;num--) {
        sum = 0;
        int N = Integer.parseInt(br.readLine());
        String[][] board = new String[N][N];
        initBoard(board, N);

        backTracking(board, N, 0);
        System.out.println(sum);
    }

}

public static void backTracking(String[][] board, int n, int x) {
    if (x == n) {
        printBoard(board, n);
        sum++;
    } else {
        for (int y = 0; y < n; y++) {
            if (check(board, n, x, y)) {
                String[][] newBoard = deepCopy(board, n);
                newBoard[x][y] = "Q";
                backTracking(newBoard, n, x + 1);
            }
        }
    }
}


// 이전것이 없는지 확인
public static boolean check(String[][] board, int n, int x, int y) {
    // \ check, / check, | check
    for (int i = 1; i <= x; i++) {
        if (x-i>=0 && y-i>=0 && board[x - i][y - i].equals("Q")) {
            return false;
        }
        if (x-i>=0 && y+i<n && board[x - i][y + i].equals("Q")) {
            return false;
        }
        if (x-i>=0 && board[x-i][y].equals("Q")) {
            return false;
        }
    }
    return true;
}

아 몬데 왜 또나는데 (찡찡

JAVA 3  >> 구조체 변경

가장 시간을 많이 먹는게 뭘까 고민햇는데

deepCopy 부분같아서  2차원 배열을 포기하기로 햇다

처음엔 맵으로 짯는데

생각해보니 구지 메모리 낭비할 필요가 잇나 싶엇다

걍 1차원 배열로 귀결

public static void backTracking(int[] board, int n, int x) {
    if (x == n) {
        printBoard(board, n);
        sum++;
    } else {
        for (int y = 0; y < n; y++) {
            board[x] = y;
            if (check(board, x)) {
                backTracking(board, n, x + 1);
            }
        }
    }
}

// 이전것이 없는지 확인
public static boolean check(int[] board, int x) {

    // \ check, / check, | check
    for (int i = 0; i < x; i++) {
        if (board[i] == board[x]) return false;
        if ((board[i] - board[x]) == (x - i)) return false;
        if ((board[x] - board[i]) == (x - i)) return false;
    }
    return true;

}

(x,y) 가 있다면

board[x] = y 인것이다

신기하게 줄이 점점 짧아진다

속도는 더 못줄일꺼같다 

여기서 종료