[DFS] Nqueen Algorithm

import java.util.Scanner;
 
// N Queen
// http://jungol.co.kr/problem.php?id=1889
public class NQueen {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] check = new int[n];
    int count =  0;
    public void queenCount(int deep){
        if(deep == n){
            count++;
            return;
        }
        for(int i = 0; i < n; i++){
            if(isUsed(deep, i)){
                check[deep] = i;
                this.queenCount(deep+1);
            }
        }
        check[deep] = 0;
        return;
    }
    public boolean isUsed(int deep, int target){
        for(int i = 0 ; i < deep; i++)
            if(check[i] == target || check[i] + (deep-i) == target ||  
                check[i] - (deep-i) == target)
                return false;
        return true;
    }
    public void display(){
        System.out.println(count);
    }
    public static void main(String[] args) {
        NQueen n = new NQueen();
        n.queenCount(0);
        n.display();
    }
}
 

 DFS 입문 문제로 유명한 NQueen 문제이다.  이것은 N을 입력받아 NxN체스판에 퀸을 N개 넣을 수 있는 경우의 수가 몇 개인가를 구하는 문제인데 여기서 많이 느낀 것이 항상 인간을 데이터를 시각화하기 위한 노력을 한다. 어떤 문제를 풀든 해당되는 맵이나 그래프 생성한 뒤 그 위에서 조건에 맞추어 조작한 후 그 시각적 데이터를 기반으로 문제를 Solved 하는데 이 NQueen은 맵을 생성하는 것이 아닌 일정한 규칙을 분석해 데이터사용과 알고리즘의 성능적 문제를 최소화 하였다.

규칙

1. 퀸은 단 한줄에 한 개밖에 넣을 수 없다.
2. 퀸을 놓았다면 차이나는 열 만큼 대각선의 위치가 발생한다. 만약 1열 1행에 퀸이 있고 3열 3행에는 퀸을 놓을 수 없는데 그 거리가 3-1만큼 차이난다는 뜻

따라서 위 코드는 함수를 총 3개로 나눠 사용했는데 이것은 변수를 줄이는 것과 코드의 논리적 구조를 명확하기 위한 것이다.

public void queenCount(int deep);
 이 함수는 DFS(Backtracking, 깊이 우선 탐색)의 핵심 함수로써 재귀적 함수 호출 방식을 통해 구현한다. 근본적인 구조는 아래와 같다.
 1. 깊이가 끝인지 탐색하는 조건코드
 2. DFS의 구조 실현을 위한 재귀적 호출을 반복하기 위한 코드
 따라서 함수를 낮은 값의 테스트케이스로 그려보면 대충 왜 깊이 우선탐색이고 왜 트리구조이며 왜 스택형식으로 되는지 알 수 있을 것이다.

public boolean isUsed(int deep, int target);
 이 함수는 해당 깊이(행)에서 해당 타겟의 자리가 가용 가능한지를 판단하는 함수이다. 이 함수는 해당 위치가 상위 행에서의 퀸의 8방향과 곂치는지 검증하며 검증하던 도중 겹치면 무조건 return false를 반환하여 해당 체크배열에 해당 타겟값을 넣는 것을 방지한다.

public void display();
 간단히 총 count를 세기 위해 실행되는 함수이다.

 check[]를 왜 사용후 0으로 초기화 해주지 않냐는 질문이 있을 수 있는데 애초에 그냥 덮어 쓰는 구조로 되어 있어 해당 부분은 신경쓰지 않아도된다. 어차피 isUsed()함수에서도 타겟의 위 열까지만 검사하므로 전혀 문제될 것이 없다.

 DFS구현할 때 왠만하면 0배열은 임시 저장소로 남겨두고 1~N까지 가용가능하도록 [N+1]로 선언하는 것이 좋다. 왜냐하면 deep과 여러가지 base value들이 보통 1부터 세기 때문이다.