백준 9663번 : N-Queen (JAVA) 문제 풀이

www.acmicpc.net/problem/9663

9663번: N-Queen

 

---

 

문제 분석

---

퀸의 공격 방향

퀸의 특성상 한줄에 하나씩 밖에 둘수가 없게 된다.

일단 먼저 N이 4라고 가정하고, 퀸을 배치해보자.

4 X 4 체스판에 [0][0] 위치에 1번째 퀸을 둔다고 하면,

1번째 퀸, [0][0]에 두는 경우

다른 퀸을 배치하지 못하는 위치(퀸의 공격을 받을 수 있는 곳)은 위의 그림 처럼 된다.

그러면 2번째 퀸을 놓을 수 있는 곳은, [1][2] 와 [1][3] 두 가지

이렇게 [1][2]와 [1][3]에 두 곳에 놓을 수 있을 것이다.

[1][2]에 놓았을 경우에는, 다음 줄에 둘 수가 없기 때문에 해답이 될 수가 없고,

[1][3]에 놓았을 경우에는, [2][1]에 둘 수가 있게 되서 다시 재귀함수를 호출하게 된다.

3번째 퀸을 [2][1]에 퀸을 두는 경우

이렇게 되면, 4번째 퀸을 둘 공간이 없기 때문에 답이 될 수가 없다.

이제 이 과정들을 반복하면 된다.

---

 

내가 생각해낸 풀이

---

일단 퀸의 위치를 저장한 이차원 배열 int[ ][ ] 와, 방문여부를 저장 할 이차원 배열 boolean[ ][ ] 두개를 선언했다.

public class Main {
    static int[][] queen;        // 퀸의 위치 표시
        static boolean[][] visit;    // 퀸을 놓을 수 있는지

        ..
}

N과 M 문제 처럼, 백트래킹을 구현해주면 된다.

public class Main {
    static int[][] queen;    // 퀸의 위치 표시
    static boolean[][] visit;    // 퀸을 놓을 수 있는지
    static int N;
    static int result = 0;

    static void dfs(int n) {
        if (n == N) {
            //arr = new int[N][N]; // 초기화
            result++;
            return;
        }


        for (int j = 0; j < N; j++) {

            if (!visit[n][j]) {
                visit[n][j] = true;
                arr[n][j] = 1;

                /* 퀸의 공격방향 체크 */

                dfs(n + 1);

                /* 이전 상태로 돌려 놓기! */
            }
        }
    }

백트래킹 기본 구조를 살펴보자면

재귀함수의 종료시점은,

n이 M과 같아지는 시점에는 M개의 퀸을 둔것이라고 판단하여 result의 값을 증가 시켜주면 된다.

• 퀸의 공격방향을 체크
• 재귀 호출을 한 다음, 다른 경우를 다 탐색하고 난 뒤, 현재의 퀸 공격위치를 다시 되돌려 놓는다.

위에 과정을 반복시켜 주면 된다.

---

퀸의 공격방향 체크

1. 퀸의 아래 방향 공격 ( for문을 이용해 앞 인덱스만 증가시켜 체크해준다.)
2. 퀸의 왼쪽 아래 대각선 방향 ( [+1] [-1] 을 시켜주면서 벽에 부딪히면 종료 시켜준다.)
3. 퀸의 오른쪽 아래 대각선 방향 ( [+1] [+1] 을 시켜주면서 벽에 부딪히면 종료 시켜준다.)

(양 옆과, 위쪽 방향에는 체크를 할 필요가 없다.)

코드

public static void check_queen_Atack(int a, int b) {
    /* 아래 방향 */
    for (int i = a; i < N; i++) {
        visit[i][b] = true;
    }
    /* 왼쪽 대각선 */
    int c = a;
    int d = b;
    while (0 <= d && d < N & 0 <= c & c < N) {
        visit[c++][d--] = true;
    }
    /* 오른쪽 대각선 */
    while ((0 <= a && a < N & (0 <= b && b < N))) {
        visit[a++][b++] = true;
    }
}

 

---

이전 상태로 되돌리기

이전 상태로 되돌리기 위해서는, 퀸의 위치를 표시해주는게 중요하다.

재귀 함수 코드 중 살펴보면,

public static void 재귀함수(int n) {

    //    생략

    for(int j=0; j < N; j++) {
        if( !visit[n][j] ) {
            visit[n][j] = true;    // 해당 인덱스 방문 처리
            queen[n][j] = 1;     // 퀸 놓은 위치 기억

            /* 퀸의 공격 방향 체크 */

            재귀함수(n + 1);    // 다음 퀸 배치

            /* 나머지 방법의 퀸 배치가 끝났다는 의미이므로, 
                다시 원상복귀 시켜 준다. */

            queen[n][j] = 0;    // 다시 퀸을 빼도록 한다.

            /* 방문 처리 했던 배열 초기화 */
            for(int p=0; p < N; p++) {
                for(int q=0; q < N; q++) {
                    if(queen[p][q] == 1) {
                        // 퀸을 두었던 곳을 다시 체크
                    }
                }
            }
        }
    }
}

 

 

전체 코드

---

 

import java.util.Scanner;

public class Main {
    static boolean[][] visit;
    static int[][] arr;
    static int N;
    static int result = 0;

    public static void dfs(int n) {
        if (n == N) {
            result++;
            return;
        }
        
        for (int j = 0; j < N; j++) {
            if (!visit[n][j]) {
                visit[n][j] = true;
                arr[n][j] = 1;

                /* 퀸의 공격방향 체크 */
                check_queen_Atack(n, j);

                dfs(n + 1);

                /* 이전 상태로 돌아가기 */
                arr[n][j] = 0;	// 퀸을 빼고,
                init_visit();	// 초기화를 시킨뒤
                
                /* 이전에 두었던 퀸의 위치 복원 */
                for (int i = 0; i < N; i++) {
                    for (int p = 0; p < N; p++) {
                        if (arr[i][p] == 1)
                            check_queen_Atack(i, p);
                    }
                }
            }
        }
    }

	/* 퀸의 공격 방향 표시하는 메소드 */
    public static void check_queen_Atack(int a, int b) {
        /* 아래 방향 */
        for (int i = a; i < N; i++) {
            visit[i][b] = true;
        }
        /* 왼쪽 대각선 */
        int c = a;
        int d = b;
        while (0 <= d && d < N & 0 <= c & c < N) {
            visit[c++][d--] = true;
        }
        /* 오른쪽 대각선 */
        while ((0 <= a && a < N & (0 <= b && b < N))) {
            visit[a++][b++] = true;
        }
    }

	/* 체스판 초기화 시키는 메소드 */
    public static void init_visit() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visit[i][j] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        visit = new boolean[N][N];
        arr = new int[N][N];
        dfs(0);
        System.out.println(result);
    }
}