[백준-9663]-[백트래킹] - N-Queen

문제 링크 : https://www.acmicpc.net/problem/9663

---

이 문제는 백트래킹 알고리즘의 기본적인 예제라고 한다. 

백트래킹 알고리즘은 그리디 알고리즘과 모든 가능성을 조회하고 조회 한 값으로 결과를 구한다는 비슷한 성질을 가진다.

차이점은 그리디 알고리즘은 정말 모든 가능성을 조회하지만 백 트래킹의 경우는 다음경우가 유효한 경우가 아니면 진행하지 않는다. 

그런 개념을 이해할 수 있는 문제가 N-Queen 문제인거 같다. 

이 문제는 퀸을 N x N 체스 판에 N 개만큼 위치 시킬 수 있는 경우의 수가 얼마만큼 있는지 구하는 문제이다.

예로 4 x 4 체스판에 (1, 2) 위치에 퀸이 놓여져 있다고 가정하면 (1번 인덱스가 제일 앞 인덱스라 할 때)

	Q

위의 빨간색인 부분에는 퀸을 놓을수 없다. 

두번째 행에는 4번째 열에 놓을수 있다. 

	Q
			Q

세번째 행에는 1번째 열에만 퀸을 놓을 수 있다.

	Q
			Q
Q

네번째 행에는 3번째 열에만 퀸을 놓을 수 있고 가능한 경우의 수 하나를 찾았다.

이렇게 i 번째 행 j번 열에 퀸을 놓았을때  i+1 행에 퀸을 놓을 수 있는 자리가 있는지 확인하고 있으면  그 다음 열에 퀸을 놓을수 있는 열을 구하면 된다.

해당 열에 퀸을 놓을 수 없으면 다음 행에도 퀸을 놓을 수 없기 때문에 유효하지 않으면 다음단계로 넘어가지 않는다.

처음 시작하는 부붙부터 차근 차근 소스를 보면서 어떻게 돌아가는지 확인해보자.

    public static int N;
    public static int count;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // 각 행에는 하나의 열에만 퀸이 놓여질 수 있다.
        // 1 열부터 N열까지 돌면서 각 1행 N열에 퀸을 놓았을때 가능한 경우를 확인한다.
        for(int i = 1; i <= N; i++) {
            int[] col = new int[N+1]; // N * N 행렬이기에 열도 인덱스를 N 까지 갖을 수 있게 한다.
            
            // 1행 i열에 퀸을 놓았다.
            col[1] = i;
            // 1행 i열에 퀸을 놓았을 경우 가능한 횟수를 dfs로 구한다.
            dfs(col, 1);
        }
        
        System.out.println(count);
    }

전역 변수로는 입력 받을 값 N 과 N x N 체스판에 N개의 퀸이 놓일 수 있는 경우의 수를 저장할 count란 변수를 선언했다.

9번째 줄 부터는 1번 행에 (1 ~ N ) 열이 위치했을 경우 N 개의 퀸이 놓일 수 있는지 dfs로 조회한다.

4 x 4 체스판이라면

1행 1열 에 퀸을 놓았을 때

1행 2열 에 퀸을 놓았을 때

1행 3열 에 퀸을 놓았을 때 

1행 4열 에 퀸을 놓았을 때 

4개의 위치에 퀸이 위치 했을때 다른 행에 N개의 퀸이 좋재 할 수 있는지 확인하는거라 이해하면 된다.

이제 dfs 소스를 보자.

    // row 행까지는 퀸을 놓았다.    
    // row+1행에 퀸을 놓을수 있는지 확인한다.
    // 만약 row 값이 N 과 같다면 N 행까지 퀸을 놓았다는 말이므로 count를 1 증가시켜준다.
    public static void dfs(int[] col, int row) {
        if(row == N) {
            count++;
        }else {
            // 1열 부터 N 열까지 반복하면서 (row+1, i)에 퀸을 놓을 수 있는경우가 있는지 확인한다.
            // 있으면 다음행의 dfs를 호출한다.
            for(int i = 1; i <= N; i++) {
                col[row+1] = i;
                if(isPossible(col, row+1)) {
                    dfs(col, row+1);
                }
            }
        }
    }

dfs의 시작은 1행 부터 시작한다고 했다.

row 행까지는 퀸이 놓였고 다음 행에 (1 ~ N)열에 퀸을 놓을 수 있는 열이 있는지 확인하고 놓을 수 있으면 다음 행이 가능한지 계속 확인 하면 된다. 

그래서 반복문의 범위를   1 ~ N 까지 지정했고 row+1 에 i 열이 위치할경우의 가능성을 확인하는 isPossible( .. ) 함수를 호출한다.

    public static boolean isPossible(int[] col, int row) {
        // 1행부터 row 행까지 같은 열 혹은 대각선에 위치하는 퀸이 있는지 확인한다.
        
        for(int i=1; i < row; i++) {
            // i 행과 row 행의 열 값이 같으면 퀸을 놓을수 없다. 
            if(col[i] == col[row]) return false;
            
            // i 행과 row 행의 열값이 대각선에 위치하는 절대값이면 안된다.
            if(Math.abs(i - row) == Math.abs(col[i] - col[row])) return false;
        }
        return true;
    }

row - 1  행까지 놓은 열의 위치로 row행이 가지고 있는 열의 값이 퀸을 놓을 수 있는 위치인지 확인한다.

col[i] == col[row] 의 경우 행은 다르지만 같은 열에 존재한다는 것이므로 유효하지 않은 위치다.

대각선에 위치한 경우 두 좌표의 y 좌표 의 차  x 좌표의 차는 같다. 

대각선에 위치한 경우에도 퀸을 놓을 수 없으니 유효하지 않은 위치다.

모든 경우에 해당 되지 않으면 true를 반환 한다.

전체 소스

import java.util.Scanner;
 
public class Main {
    public static int N;
    public static int count;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // 각 행에는 하나의 열에만 퀸이 놓여질 수 있다.
        // 1 열부터 N열까지 돌면서 각 1행 N열에 퀸을 놓았을때 가능한 경우를 확인한다.
        for(int i = 1; i <= N; i++) {
            int[] col = new int[N+1]; // N * N 행렬이기에 열도 인덱스를 N 까지 갖을 수 있게 한다.
            
            // 1행 i열에 퀸을 놓았다.
            col[1] = i;
            // 1행 i열에 퀸을 놓았을 경우 가능한 횟수를 dfs로 구한다.
            dfs(col, 1);
        }
        
        System.out.println(count);
    }
    // row 행까지는 퀸을 놓았다.    
    // row+1행에 퀸을 놓을수 있는지 확인한다.
    // 만약 row 값이 N 과 같다면 N 행까지 퀸을 놓았다는 말이므로 count를 1 증가시켜준다.
    public static void dfs(int[] col, int row) {
        if(row == N) {
            count++;
        }else {
            // 1열 부터 N 열까지 반복하면서 (row+1, i)에 퀸을 놓을 수 있는경우가 있는지 확인한다.
            // 있으면 다음행의 dfs를 호출한다.
            for(int i = 1; i <= N; i++) {
                col[row+1] = i;
                if(isPossible(col, row+1)) {
                    dfs(col, row+1);
                }
            }
        }
    }
    
    public static boolean isPossible(int[] col, int row) {
        // 1행부터 row 행까지 같은 열 혹은 대각선에 위치하는 퀸이 있는지 확인한다.
        
        for(int i=1; i < row; i++) {
            // i 행과 row 행의 열 값이 같으면 퀸을 놓을수 없다. 
            if(col[i] == col[row]) return false;
            
            // i 행과 row 행의 열값이 대각선에 위치하는 절대값이면 안된다.
            if(Math.abs(i - row) == Math.abs(col[i] - col[row])) return false;
        }
        return true;
    }
}