백준/9663 N-Queen / dfs + 백트래킹

N-Queen 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

10 초

128 MB

79587

38362

25007

47.086%

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

예제 입력 1 복사

8

예제 출력 1 복사

92

---

풀이

공격범위체크함수를 만들어야겠다 -> 퀸을 어느 인덱스에 놓았는지 체크하는 일차원배열을 만들어야겠다 -> dfs로 깊이우선탐색을 하다 놓을곳이없다면 멈추는 백트래킹을 해야겠다.

 

공격범위체크함수 -> 2차원 boolean[][] 로 공격범위 변수를 만들어야겠다. -> 해당 위치에 퀸을 놓고, 안놓고의 경우를 만들어야하니까 놓았을때의 공격범위 2차원배열을 생성해주는 함수를 만들자 

 

구현 -> 메모리초과

 

2차원배열 생성해주는 부분에서 메모리가 초과됬을것이다.

 

하나의 2차원배열을 사용하되 공격범위 체크했던걸 다시돌리는 함수를 만들자.

 

 

틀린코드

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int result ;
    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        int[] queenPosition = new int[n];
        boolean[][] atackRange = new boolean[n][n];

        dfs(n, atackRange, queenPosition, 0);
        bw.write(result+"");



        bw.flush();
        bw.close();

    }
    public static void dfs(int n,boolean[][] atackRange,int[] queenPosition,int i) {
        if (i == n) { //마지막줄까지 이동했을때
            result++;
            return;
        }

        for (int a = 0; a < n; a++) {
            if (!atackRange[i][a]) { //만약 공격범위가 아니라면
                queenPosition[i] = a; //해당 위치에 퀸을 놓고 , 퀸의 위치를 저장한다.

                //방금놓은 퀸의 공격범위를 추가 적용해준 새로운 공격범위 배열을 만들어서 넘긴다.
                boolean[][] atackRangeAdded = atack(atackRange, i, a);

                dfs(n, atackRangeAdded, queenPosition, i + 1); // 공격범위업데이트,퀸 위치 추가 , 다음열로 이동 시켜서 dfs호출
                queenPosition[i] = 0; //퀸 위치 초기화 (이 자리에 안놓은 경우 생성)

            }
        }
        // 다 돌았는데 퀸을 놓을 수 있는 자리가 없어서 퀸의 위치가 0이라면
        if (queenPosition[i] == 0) {
            return; //더 보지않고 return
        }


    }





    public static boolean[][] atack(boolean[][] atackRange,int i,int j) {
        int n = atackRange.length; // 길이

        boolean[][] copyAtackRange = new boolean[n][n];

        for (int a = 0; a < n; a++) {
            for (int b= 0; b < n; b++) {
                copyAtackRange[a][b] = atackRange[a][b];
            }
        }

        // 자기자신위치 , 왼쪽대각선아래, 아래, 오른쪽 대각선아래를 공격범위로 채워준다.
        copyAtackRange[i][j] = true; //자기자신

        int nextI = i;
        int nextJ = j;
        //왼쪽 대각선 아래
        while (true) {
            nextI = nextI + 1;
            nextJ = nextJ - 1;
            if (nextI >= n || nextJ < 0) {
                break;
            }
            copyAtackRange[nextI][nextJ] = true;
        }
        nextI = i;
        nextJ = j;
        //오른쪽 대각선 아래
        while (true) {
            nextI = nextI + 1;
            nextJ = nextJ + 1;
            if (nextI >= n || nextJ >= n) {
                break;
            }
            copyAtackRange[nextI][nextJ] = true;
        }
        nextI = i;
        nextJ = j;
        //아래
        while (true) {
            nextI = nextI + 1;
            if (nextI >= n) {
                break;
            }
            copyAtackRange[nextI][j] = true;
        }

        return copyAtackRange;
    }


}

 

 

방금 놓은 퀸의 공격범위를 지우는 함수 생성- >  공격범위 체크했던걸 그대로 다시 돌려놓으려고 범위 그대로 false처리했더니 이전 퀸의 공격범위까지 false 처리되는 경우가 생겨서 문제발생.

 

 

해결방법 -> boolean[][] 2차원 배열의 전체를 false로 초기화하고 다시 이전 퀸위치를 받아와 공격범위 설정

한번 싹 초기화 시키고, 다시 하나씩 퀸위치받아와서 공격범위 설정해주었다.

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int result ;
    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        int[] queenPosition = new int[n];
        boolean[][] atackRange = new boolean[n][n];

        dfs(n, atackRange, queenPosition, 0);
        bw.write(result+"");



        bw.flush();
        bw.close();

    }
    public static void dfs(int n,boolean[][] atackRange,int[] queenPosition,int i) throws IOException{
        if (i == n) { //마지막줄까지 이동했을때
//            for (int cu : queenPosition) {
//                bw.write(cu + " ");
//            }
//            bw.newLine();
            result ++;
            return;
        }

        for (int a = 0; a < n; a++) {
            if (!atackRange[i][a]) { //만약 공격범위가 아니라면
                queenPosition[i] = a; //해당 위치에 퀸을 놓고 , 퀸의 위치를 저장한다.

                //방금놓은 퀸의 공격범위를 추가
                atack(atackRange, i, a);

                dfs(n, atackRange, queenPosition, i + 1); // 공격범위업데이트,퀸 위치 추가 , 다음열로 이동 시켜서 dfs호출

                queenPosition[i] = -1; //퀸 위치 초기화 (이 자리에 안놓은 경우 생성)

                //공격범위 체크했던거 되돌려놓기
                cleanAtackRange(atackRange, queenPosition,i, a);

            }
        }
        // 다 돌았는데 퀸을 놓을 수 있는 자리가 없어서 퀸의 위치가 0이라면 (해당 열이 모두 공격범위라서 못놓았을때)
        if (queenPosition[i] == -1) {
            return; //더 보지않고 return
        }


    }





    public static void atack(boolean[][] atackRange,int i,int j)throws IOException {
        int n = atackRange.length; // 길이

        // 자기자신위치 , 왼쪽대각선아래, 아래, 오른쪽 대각선아래를 공격범위로 채워준다.
        atackRange[i][j] = true; //자기자신

        int nextI = i;
        int nextJ = j;
        //왼쪽 대각선 아래
        while (true) {
            nextI = nextI + 1;
            nextJ = nextJ - 1;
            if (nextI >= n || nextJ < 0) {
                break;
            }
            atackRange[nextI][nextJ] = true;
        }
        nextI = i;
        nextJ = j;
        //오른쪽 대각선 아래
        while (true) {
            nextI = nextI + 1;
            nextJ = nextJ + 1;
            if (nextI >= n || nextJ >= n) {
                break;
            }
            atackRange[nextI][nextJ] = true;
        }
        nextI = i;
        nextJ = j;
        //아래
        while (true) {
            nextI = nextI + 1;
            if (nextI >= n) {
                break;
            }
            atackRange[nextI][j] = true;
        }
    }
    public static void cleanAtackRange(boolean[][] atackRange,int[] queenPosition,int i,int j) throws IOException{
        int n = atackRange.length;
        //전부 false로 초기화 시키고
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                atackRange[a][b] = false;
            }
        }
        // 이전 퀸 위치를 받아 다시 공격범위 설정
        for (int c = 0; c < n; c++) {
            if (queenPosition[c] != -1) { //-1로 초기화하기전 퀸 위치에 관하여 공격범위 설정
                atack(atackRange, c, queenPosition[c]);
            }
        }
    }



}

 

 

 

다른사람풀이

2차원을 1차원적으로 생각해서 풀이하였다.

훨씬 깔끔하긴하지만 저렇게 생각하기 쉽지않을듯 하다.

https://st-lab.tistory.com/118