[9663]N-Queen (Backtracking)

Backtracking (되추적)

---

말이 존나어려운데 쉽게 말하면

어떤 노드의 유망성 점검후 유망하지않으면 그 노드의 부모 노드로 되돌아간다

예를들면 어떤길을 따라 쭉 가는데 길이 막혀있으면 마지막으로 만났던 갈림길로 되돌아가서 다른길로 가는거를 생각하면 되겠다.

Stack을 이용

자세한글은 https://idea-sketch.tistory.com/29 이분의 글을 참조

import java.util.Scanner;
import java.util.Stack;
 
class Point {
    
    private int x;
    private int y;
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
}
 
public class Main {
 
    public static void main(String[] args) {
        
        int chessBoardSize = inputValueScanner();
        int[][] chessBoard = makeChessBoard(chessBoardSize);
        Stack<Integer> hopefulPointStack = new Stack<>();
        int chessBoardLen = chessBoard[0].length;
        int n_QueenPlaceCount = 0;
 
        firstHopefulPointInsert(hopefulPointStack, chessBoardLen);
        
        first:while( !hopefulPointStack.isEmpty() ){
            
            int hopefulPointX = hopefulPointStack.pop();
            int hopefulPointY = hopefulPointStack.pop();
            Point hopefulPoint = new Point(hopefulPointX, hopefulPointY);
            
            chessBoard[hopefulPointX][hopefulPointY] = hopefulPointX + 1;
            boolean checkPlaceableQueenSeat = false;
            
            for(int queenCount = hopefulPointX; queenCount < chessBoardLen;){
                
                setLeftBottomDiagonalXvalueOfChessBoard(hopefulPoint, chessBoard);
                setCenterBottomStraightXvalueOfChessBoard(hopefulPoint, chessBoard);
                setRightBottomDiagonalXvalueOfChessBoard(hopefulPoint, chessBoard);
                
                queenCount++;
                
                // 퀸을 각 줄에 1개씩 다놓았을때
                if( queenCount == chessBoardLen){
                    n_QueenPlaceCount++;
                    // 체스판 초기화 코드 넣어야함
                    if(!hopefulPointStack.isEmpty()){
                        resetFlagIfUnplaceableQueen(hopefulPointStack.peek(), chessBoard);
                    }
                    break;
                }
                
                for(int y = chessBoardLen - 1; y >= 0; y--){
                    // 다음줄에 퀸을 놓을수있는지 확인
                    if( chessBoard[queenCount][y] == 0){
                        checkPlaceableQueenSeat = true;
                        hopefulPointStack.push(y);
                        hopefulPointStack.push(queenCount);
                    }
                }
                
                // 퀸을 놓을자리가 없다면
                if(!checkPlaceableQueenSeat){                    
                    if(!hopefulPointStack.isEmpty()){
                        resetFlagIfUnplaceableQueen(hopefulPointStack.peek(), chessBoard);
                    }
                }
                                
                break;
            }
        }
        
        System.out.println(n_QueenPlaceCount);
    }
    
    public static int inputValueScanner(){
        Scanner scan = new Scanner(System.in);
        return scan.nextInt();
    }
    public static int[][] makeChessBoard(int chessBoardSize){
        return new int[chessBoardSize][chessBoardSize];
    }
    
    public static void firstHopefulPointInsert(Stack<Integer> hopefulPointStack, int chessBoardLen){
        for(int i = chessBoardLen - 1; i >= 0; i--){
            hopefulPointStack.push(i);
            hopefulPointStack.push(0);
        }
    }
    
    public static void setLeftBottomDiagonalXvalueOfChessBoard(Point hopefulPoint, int[][] chessBoard){
        
        int hopefulPointX = hopefulPoint.getX();
        int minusYvalueContain = hopefulPoint.getY();
 
        for(int x = hopefulPointX; (x + 1) < chessBoard[0].length; x++){
            for(int y = minusYvalueContain; (y - 1) >= 0;){
                if( chessBoard[x+1][y-1] == 0){
                    chessBoard[x+1][y-1] = hopefulPointX + 1; 
                }
                
                minusYvalueContain = y-1;
                break;
            }
        }
    }
    
    public static void setCenterBottomStraightXvalueOfChessBoard(Point hopefulPoint, int[][] chessBoard){
        
        int hopefulPointY = hopefulPoint.getY();
        int hopefulPointX = hopefulPoint.getX();
        
        for(int x = hopefulPoint.getX(); (x + 1) < chessBoard[0].length; x++){
            if( chessBoard[x+1][hopefulPointY] == 0){
                chessBoard[x+1][hopefulPointY] = hopefulPointX + 1;
            }
        }
    }
    
    public static void setRightBottomDiagonalXvalueOfChessBoard(Point hopefulPoint, int[][] chessBoard){
        
        int hopefulPointX = hopefulPoint.getX();
        int plusYvalueContain = hopefulPoint.getY();
        
        for(int x = hopefulPointX; (x + 1) < chessBoard[0].length; x++){
            for(int y = plusYvalueContain; (y + 1) < chessBoard[0].length;){
                
                if( chessBoard[x+1][y+1] == 0){
                    chessBoard[x+1][y+1] = hopefulPointX + 1;                     
                }
                plusYvalueContain = y + 1;
                break;
            }
        }
    }
    
    public static void resetFlagIfUnplaceableQueen(int flagValue, int[][] chessBoard){
        
        for(int x = flagValue; x < chessBoard[0].length; x++){
            for(int y = 0; y < chessBoard[0].length; y++){
                if( chessBoard[x][y] > flagValue){ // 다시 처음부터 해야한다면 다지워야하니 값보다 큰건 다지움
                    chessBoard[x][y] = 0;
                }
            }
        }
    }
 
}

위 코드의 핵심은 Stack이다.

스택안에 유망한 노드의 좌표를 넣어서 막힐때마다 스택안의 값을 꺼내어 다시 계산한다 

최대한 클린코드가 말한대로 나름 신경써서 코드를 작성했기에 

먼 미래의 내가 볼때도 제발 무리가 없길 바란다.