백준 2239 스도쿠 java (백트래킹 재귀종료 설정)

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

백트래킹으로 체크하면서 퍼즐을 채워나가는 문제.

특별할 것 없는 문제지만, 여러케이스가 가능할 경우에는 모든 칸을 순서대로 한 81자리 수가 가장 작은 케이스만 출력하라는 조건이 있다.

1~9 순서로 넣어보다가 처음 9*9가 완성된 순간만 출력하고 뒤에는 출력하지 말라는 의미.

기존에는 조건을 달성했을 때 실행되는 출력함수 속에 System.exit(0); 을 실행시켜 강제종료 시켰지만

백트래킹 재귀를 깔끔하게 종료시키는 방식으로 구현하고 싶어졌다.

 

재귀적으로 각 칸에 함수를 실행할 때 상황에 따라 다른 bool 값을 return 처리하면서 구현했다.

특정 칸에서 1~9를 다 넣어봐도 안되면 false를 반환하며 그앞에서 다른값을 시도 해 볼 것이고

끝까지 가서 조건을 만족시킨경우 true가 return 되면, 앞선 함수들에서도 연쇄적으로 true가 return 되면서

추가적인 출력과 재귀호출이 발생하지 않는다.

    import java.lang.reflect.Array;
    import java.util.*;
    import java.io.*;
    import java.lang.*;

    public class Main {
        static int[][] arr = new int[9][9];
        static void print(){
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    sb.append(arr[i][j]);
                }
                sb.append("\n");
            }
            sb.deleteCharAt(sb.length()-1);
            System.out.print(sb);
        }
        static boolean solve(int row,int col){
            if(col==9){
                col=0;row++;
            }
            if (row == 9) {
                print();
                return true;
            }
            if(arr[row][col]==0) {
                for (int i = 1; i <= 9; i++) {
                    arr[row][col] = i;
                    if (check(row, col)) {
                        if(solve(row, col + 1)){
                            return true;
                        }
                    }
                    arr[row][col] =0;
                }
            }
            else{
                return solve(row,col+1);
            }
            return false;
        }
        static boolean check(int row,int col){
            boolean[] check = new boolean[10];
            for(int i=0;i<9;i++){
                int temp = arr[row][i];
                if(temp!=0){
                    if(check[temp]){
                        return false;
                    }
                    else{
                        check[temp]=true;
                    }
                }
            }
            Arrays.fill(check,false);
            for(int i=0;i<9;i++){
                int temp = arr[i][col];
                if(temp!=0){
                    if(check[temp]){
                        return false;
                    }
                    else{
                        check[temp]=true;
                    }
                }
            }
            Arrays.fill(check,false);
            int squarerow=row/3*3;
            int squarecol=col/3*3;
            for(int i=squarerow;i<squarerow+3;i++){
                for(int j=squarecol;j<squarecol+3;j++){
                    int temp = arr[i][j];
                    if(temp!=0){
                        if(check[temp]){
                            return false;
                        }
                        else{
                            check[temp]=true;
                        }
                    }
                }
            }
            return true;
        }
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            for(int i=0;i<9;i++){
                String str = br.readLine();
                for(int j=0;j<9;j++){
                    arr[i][j]= Integer.parseInt(str.substring(j,j+1));
                }
            }
            solve(0,0);
        }
    }