백준_9663_N-Queen

한동안 jdbc부터 시작해서 웹 쪽 언어를 공부하다 보니 시간이 부족해서 알고리즘을 풀이만 하고, 따로 정리를 하지 못했다. 살살 귀찮을 뻔 했는데, 다시 마음을 잡고 시작해보려 한다.  

이번 문제는 백준 단계별로 문제 풀기 중 백트레킹 카테고리에 있는 골드5 문제로, 완전탐색과 백트레킹을 응용하는 문제이다. 

필자는 처음 완전탐색으로 풀어보려다가 애매하게 재귀를 섞어서 백트레킹을 쓰다보니 문제가 풀리지 않아서 한 참을 헤맸다. 

이후에는 재귀를 사용해서 백트레킹으로 풀었는데 메모리 초과가 나서 마음이 흔들렸지만,,,, 멘탈을 잡고 다시 수정해서 결국에 성공했다. 

문제를 풀기 위해 생각한 의사코드는 다음과 같다. 

• 퀸의 이동 가능한 위치를 일일히 방문처리를 미리 해야 하나? 
  • 사실 이 방법으로 처음에 완전탐색을 진행했지만, 재귀를 올바르게 구현하지 못해 결과값 조차 제대로 나오지 못했다. 
  • 이후에는 백트레킹을 사용해서 일일히 방문 처리를 하지 않고, 배치한 퀸의 위치를 2차원 배열에 저장하고, 새롭게 퀸을 배치하고자 하는 위치와 이전에 배치한 퀸의 위치를 비교하면서 배치할 수 있는지 유무에 대한 유망성을 검사했다. 
• 유망성 체크 
  • 필자는 각 행에는 반드시 하나의 퀸 만 존재할 수 없다는 점을 파고 들었다. 당연한 이야기이지만, 같은 행의 두 개의 퀸을 놓을 수 없으므로, 재귀의 깊이 값을 행으로 사용해서  한 행에 퀸을 배치하면 다음 행(깊이)으로 재귀하도록 구현했다. 이렇게 하면 유망성을 체크할 때, 같은 행에 퀸이 존재하는지는 검사하지 않아도 된다. 
  • 수직선 체크 : 새롭게 배치하고자 하는 퀸의 열값이 이전에 배치한 퀸의 열과 같을 수 없다. 
  • 대각선 체크 : 새롭게 배치하고자 하는 퀸과 이전에 배치한 퀸의 열값의 차이 == 행값의 차이라면 배치할 수 없다. 
    • 체스판을 2차원 좌표명면에 올려서 생각해보자. 문제에서 따져야 하는 대각선의 개념은 기울기가 1 or -1인 1차원 직선이 아닌가? 이 말은 x값의 증분 = y값의 증분이 1로 동일하다는 뜻이다. 
    • 결국 x(행)값의 차이와 y(열)값의 차이가 동일하다면 같은 직선 -> 대각선 상에 존재한다는 뜻이다.
• 각 행에 대해 하나의 퀸만 배치하고 배치가 성공했으면, 깊이(행)+1을 하여 재귀를 시작한다. 
  • 깊이가 n과 같아지면 경우의수를 1증가 하고, 뒤로 돌아가면서 다른 경우의수를 탐색한다. 
  • 이때, 필자는 재귀 호출을 당하고 돌아와서 처음에 1로 퀸의 위치를 표현했지만, 이를 다시 지워주지 않아서 경우의수가 정확하게 탐색하지 못했다. 반드시 지워주어야 한다.
• 자료구조는 list를 사용했지만, 메모리 초과가 발생했다. 
  • 리스트에 사용자 정의 클래스로 pos(int x, int y)의 형식으로 저장했는데, n=15일 때, 리스트에 데이터를 삽입하기 위해서 생각 보다 엄청나게 많은 위와 같은 객체를 생성해서 리스트에 저장했다. 문제는 저장한 객체가 모두 퀸의 위치가 되는 것이 아니라, 퀸의 위치의 후보라는 것이다. 퀸의 위치를 저장하면서 깊이를 내려가지만, 다음 행의 퀸을 배치할 수 없는경우 즉, n개의 퀸을 배치하지 못한 경우에는 다시 돌아가면서 생성하여 저장한 객체를 삭제해 주어야 한다. 그래서 필자는 2차원 배열로 구현했다. 

 

package BackTracking;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class _9663_NQUEEN {
    static int n;
    static int count;
    static int [][]queen; 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        queen = new int[n][n];
        
        //한 줄에는 반드시 하나의 퀸만 존재할 수 있기때문에, 첫 째줄을 기준으로 재귀 탐색을 진행한다. 
        //(첫 줄에 퀸을 위치시킬 위치의 열값 지정) 
        for(int i=0; i<n; i++) {
            queen[0][i] = 1;//퀸의 위치만 1로 지정
            dfs(1);
            
            //하나의 기준점에서 탐색이 끝났다면 자료구조 초기화
            queen[0][i]=0;
        }
        
        System.out.println(count);
        
    }
                                            //깊이이자 행
    private static void dfs(int depth) {
        // TODO Auto-generated method stub
        if(depth == n) {
            count++;
            return;
        }
        //저장하고자 하는 위치를 기준으로 유망성을 검사하는 메소드를 생성하고 조건을 만족하면 퀸의 위치를 저장하도록 하자. 
        for(int i=0; i<n; i++) {
            if(check(depth, i)) {
                
                //새로 배치할 퀸의 위치 저장
                queen[depth][i]=1;
                
                dfs(depth+1);
                queen[depth][i]=0;
            }
        }
    }
    
    //유망성 체크
    private static boolean check(int row, int col) {
        // TODO Auto-generated method stub
        
        for(int i=0; i<n; i++) {
            for(int k=0; k<n; k++) {
                
                //      행  열
                if(queen[i][k]==1) {
                    
                    //대각선 상에 존재하는지 
                    //두 좌표의 열의 값 차이와 행의 값 차이가 동일하다면 대각선 상에 존재한다. 
                    //행은 계속 깊숙한 곳으로 내려가면서 커져가므로 음수가 될 수없지만 
                    //열은 음수가 될 가능성이 있기 때문에 절댓값을 취해야 한다.
                    if((row-i) == Math.abs(col-k)) return false;
                    
                    //상하 직선 상에 존재하는지 단 하나의 퀸과도 같은 열에 있다면 안 된다. 
                    if(k == col) return false;
                    //좌우 직선 상에 존재하는지
                    //퀸을 한 행에 하나씩만 배치하도록 구현되어 있기 때문에 좌우에는 존재할 수도 없고 검사할 필요도 없음
                }
                
            }
        }
        return true;
    }
}