백준 9663번 - N－Queen (JAVA)

문제 링크

 

 

 

문제 풀이 과정

체스 규칙을 잘 모르면 이 문제를 처음 접했을 때 난감할 수 있다.

사실 체스 규칙을 전혀 몰라서 퀸의 움직임에 대해서 먼저 검색했었다.

 

 

퀸은 오른쪽, 왼쪽, 위, 아래, 대각선으로 움직일 수 있다.

 

 

 

첫번째 퀸의 위치가 (0, 1) 일때 엑스 친 부분은 퀸이 공격 가능한 위치이다.

 

 

이 문제는 서로 다른 퀸이 공격 못하게 배치해야 되므로 다음 퀸의 자리는 (1, 3) 이 된다.

 

 

3번째 줄에는 퀸을 둘 수 있는 곳이 한곳밖에 없다.

 

4번째 퀸까지 배치가 가능하므로 서로다른 퀸이 공격 못하게 하는 위치가 된다.

 

대부분 구글에서는 1차원 배열로 풀이 하였지만, 1차원 배열보다는 직관적인 2차원배열이 이해가 잘되서 2차원 배열로 풀이 하였다.

퀸이 공격이 가능한 자리를 표시하는 visited 배열과 퀸이 놓여 있는 위치를 별도로 관리하는 이차원 배열을 만들었다.

 

 

public static void attack(int a, int b){
    for (int i = a; i < n; i++) { // 아래쪽
        visited[i][b] = true;
    }

    int c = a;
    int d = b;
    while (0 <= d && d < n & 0 <= c & c < n) { //대각선
        visited[c++][d--] = true;
    }
    while ((0 <= a && a < n & (0 <= b && b < n))) {
        visited[a++][b++] = true;
    }
}

 

퀸이 공격 가능한 위치를 찾는 메소드를 별도로 구현하였다.

 

for (int i = 0; i < n; i++) {
        if(!visited[depth][i]){
            visited[depth][i] = true;
            Q[depth][i] = 1; // 현재 퀸의 위치

            attack(depth, i); // 현재 퀸의 위치에서 공격 가능한 위치
            dfs(depth + 1); // 현재 퀸의 위치에서 다음 행의 위치 탐색

            visited[depth][i] = false;
            Q[depth][i] = 0; // 퀸을 다음칸으로 움직이기 위해 현재 퀸의 자리를 제거

            for (int j = 0; j < n; j++) {
                Arrays.fill(visited[j], false); // 체스판 초기화
            }

            for (int j = 0; j < n; j++) { // 7번 줄에서 탐색하기 전 체스판으로 되돌리는 과정
                for (int k = 0; k < n; k++) {
                    if(Q[j][k] == 1){
                        attack(j, k);
                    }
                }
            }
        }
    }

 

 

탐색을 마치고 나면 체스판이 공격 하기 전으로 되돌려 놔야하는데 여기서 많은 방법으로 고민하게 되었다.

이차원 배열을 복제하는 방법으로 풀이 하였는데 배열 복제 하는 과정에서 배열의 주소가 충돌 되어 값이 중간에 바뀌게 되었다.

왜 깊은 복사를 하는데 충돌이 날까 하고 좌절하다가 구글의 도움을 받았다.

 

현재 퀸의 위치를 알면 공격 위치를 다시 찾을 수 있다. 그래서 현재 퀸의 위치를 별도로 관리하는 배열을 만들었다. 탐색을 마치면 탐색했던 퀸의 위치를 제거하고 다시 체스판에 퀸이 있는 위치에 다시 공격이 가능한 위치를 표시하였다.

 

여기서 배열을 초기화 하기 위해서 new 생성자를 이용해봤지만, 이렇게 하게 메모리 초과가 된다.

 

 

 

 

전체코드