[BOJ - JAVA] 9663 - N-Queen (백트래킹)

# 주소

https://www.acmicpc.net/problem/9663

9663번: N-Queen

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main {
    static int n;
    static int arr[];
    static int count = 0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n];
        nqueen(0);
        System.out.println(count);
    }
    public static void nqueen(int cnt){
        if(cnt == n){
            count++;
            return;
        }
        for(int i = 0; i < n; i++){
            arr[cnt] = i;
            if(possibility(cnt)){
                nqueen(cnt+1);
            }
        }
    }
    public static boolean possibility(int t){
        for(int i = 0; i < t; i++){
            if(arr[t] == arr[i]){
                return false;
            }
            else if(Math.abs(t - i) == Math.abs(arr[t] - arr[i])){
                return false;
            }
        }
        return true;
    }
}

체스를 잘 몰라서 룰을 좀 찾아야 했습니다.

그래서 다른 분의 블로그도 많이 참고를 했습니다.. ㅠㅠ

체스에서 퀸을 움직이게 할 수 있는 여러 칸들 중에서 절대 이동경로에 없는 경우의 수를 구하는 문제입니다.

문제에서는 8개의 퀸을 주었고 이 8개의 퀸을 적절히 배치하여, 서로 이동경로상에 없게끔 배치하면 됩니다.

 

따라서, 코딩을 먼저 한 번 보시겠습니다.

일단 n을 입력받고 arr를 n크기로 선언합니다.

그리고 nqueen(0)을 실행하는데, nqueen은 dfs로 사용할 것입니다.

dfs란 깊이 우선 탐색으로서, 여기선 그 중에서도 백트래킹 기법을 이용합니다.

만약 백트래킹이 무엇인지 모르신다면, 백트래킹은 "지나가다가 여기가 아니면 취소하고 뒤돌아가는" 의미로 이해하시면 좋겠습니다.

자. 백트래킹을 구현할 때는 dfs 구문 내에 cnt(놓을 수 있는 횟수) 가 n이 되는지. 만약 만족한다면 count를 증가시키고 return시킵니다.

그리고 그렇지 못할 경우 for문에서, arr의 현재 cnt를 i로 저장합니다. 그리고 그 cnt가 과연 어떤 값을 가질 수 있을지 모르잖아요?

그래서 possibility를 통해 검증을 합니다.

만약 이 메서드에 cnt를 넣어서 참이라면 재귀함수 nqueen에 (cnt+1)을 해줄테고 아니라면 for문의 i를 증가시킵니다.

자 무슨말일까요??

안와닿으시겠지만 이렇게 이해해 봅시다.

퀸	-	-	-
-
-
-

0행0열에 퀸을 놓았습니다.

그럼 1열에 퀸을 두어야 할텐데, 어디에 두어야 할지 모르잖아요??? 

그래서 posibility를 통해 검증을 하는 것입니다.

지금 제일 먼저 들어갈 cnt값은 0입니다.

근데, 0은 arr[0]이 제일 먼저 선점해서 들어가 있는 상태이므로 cnt는 0을 생략하고 1을 검증할 것입니다.

그러나 arr[1] = 1이 되어버리면 possibility에서 두번째 else if문에서 대각선의 길이가 행의 값의 차이와 같아지므로(대각선에 있으므로) arr[1]은 0도 안되고 1도 안되니 건너 띄워집니다.

그럼 arr[1] 은 for문에 의해 그 다음 숫자가 되는 것입니다. 자, i가 2일땐 어떻나요?

그럼 표가 이렇게 됩니다.

퀸	-	-	-
-	-	-
-	퀸	-	-
-	-	-

이렇게 그려질 것입니다.

근데 이렇게 배치를 해버리면 n개의 체스를 놓을 수 없습니다.

2열에 어떤 체스도 놓을 수 없기 때문입니다.

따라서 0행0열에 퀸을 놓으면 안되게 됩니다.

그러므로 다시 실행했던 재귀함수가 돌아오면서(백트래킹 되면서) 이번엔 1행 0열에 퀸을 놓습니다.

-	-	-	-
퀸	-	-	-
-
-

이런식으로 말이지요.

그럼 1열엔 어디에 퀸을 둘 수 있나요?

-	-	-	-
퀸	-	-	-
-	-
-	퀸	-	-

이렇게 되겠지요. 더 나아가서 

-	-	퀸	-
퀸	-	-	-
-	-	-	퀸
-	퀸	-	-

이렇게 놓을 수도 있을 것입니다.

이것이 첫번째 count가 됩니다. 

그리고 다시 return하여 이번엔 0행 3열에 퀸을 놓습니다.

그럼 다음과 같이 전개될 것입니다.

-	퀸	-	-
-	-	-	퀸
퀸	-	-	-
-	-	퀸	-

그럼 0행 3열에 퀸을 두면 어떻게 될까요?

-	퀸	-	-
-	-	-	퀸
-	-	퀸	-
퀸	-	-	-

아마 이렇게 전개가 되어야 하지만, 3행 1열의 퀸과 2행 2열의 퀸이 대각선상에 있기 때문에 possibility에서 false판정을 받고, count에 포함이 되지 않을 것입니다.

 

이해가 가셨나요?

대각선상에 있을 땐 Math.abs(t-i) == Math.abs(arr[t] - arr[i]) 구문을 잘 기억하면 좋겠습니다.

감사합니다.