[백준] 2239번 스도쿠 (gold 4

import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    static ArrayList<Point> arr=new ArrayList<>();
    static int[][] map=new int[10][10];
    static boolean find=false;
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));StringTokenizer st;
        for(int i=1; i<=9; i++){
            String a=br.readLine();
            for(int j=1; j<=9; j++) {
                map[i][j]=a.charAt(j-1)-'0';
                if(map[i][j]==0){
                    arr.add(new Point(j,i));
                }
            }
        }
		//dfs에서 조건들을 확인하며 하나씩 채워나감.
        dfs(0, arr.size());

        for(int i=1; i<=9; i++){
            for(int j=1; j<=9; j++){
                bw.write(map[i][j]+"");
            }
            bw.write("\n");
        }
        bw.flush();


    }

    public static void dfs(int depth, int size){
        if(depth==size){
            find=full();
            return;
        }
        Point temp=arr.get(depth);
        for(int i=1; i<=9; i++){
            if((row(i,temp.x)==true && col(i,temp.y)) && (check(i,(temp.y-1)/3, (temp.x-1)/3)==true)) {
                map[temp.y][temp.x] = i;
                dfs(depth + 1, size);
                //찾지 못한 경우, 그자리를 초기화하여야함. 그래야 돌아가서 다른 수들 넣었을때
                //혼란 x
                if (!find) {
                    map[temp.y][temp.x] = 0;
                }
                //찾은경우는 return을 하면서 빠져나감.
                
                else{
                    return;
                }
            }
        }


    }


    //열
    public static boolean row(int n , int col){
        boolean is=true;
        for(int i=1; i<=9; i++){
            if(map[i][col]==n){
                is=false;
                break;
            }
        }
        return is;
    }
    //행
    public static boolean col(int n, int row){
        boolean is=true;
        for(int i=1; i<=9; i++){
            if(map[row][i]==n){
                is=false;
                break;
            }
        }
        return is;
    }
    //9개 칸 겹치는지 확인.
    public static boolean check(int n,int row ,int col){
        boolean is=true;
        row= (row+1)*3;
        col= (col+1)*3;
        for(int i=row-2; i<=row; i++){
            for(int j=col-2; j<=col; j++){
                if(map[i][j]==n){
                    is=false;
                    break;
                }
            }
        }
        return is;
    }


    //꽉찼는지 확인
    public static boolean full(){
        boolean is=false;
        int answer=0;
        for(int i=1; i<=9; i++){
            for(int j=1; j<=9; j++){
                if(map[i][j]!=0){
                    answer++;
                }
            }
        }
        if(answer==81){
            is=true;
        }
        return is;
    }
}

import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    static ArrayList<Point> arr=new ArrayList<>();
    static int[][] map=new int[10][10];
    static boolean find=false;
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));StringTokenizer st;
        for(int i=1; i<=9; i++){
            String a=br.readLine();
            for(int j=1; j<=9; j++) {
                map[i][j]=a.charAt(j-1)-'0';
                if(map[i][j]==0){
                    arr.add(new Point(j,i));
                }
            }
        }

        dfs(0, arr.size());

        for(int i=1; i<=9; i++){
            for(int j=1; j<=9; j++){
                bw.write(map[i][j]+"");
            }
            bw.write("\n");
        }
        bw.flush();


    }

    public static void dfs(int depth, int size){
        if(depth==size){
            find=true;
            return;
        }
        Point temp=arr.get(depth);
        for(int i=1; i<=9; i++){
            if(rowCol(i,temp.x,temp.y)==true && check(i,(temp.y-1)/3, (temp.x-1)/3)==true) {
                map[temp.y][temp.x] = i;
                dfs(depth + 1, size);
                if(find){
                    return;
                }
                map[temp.y][temp.x]=0;
            }
        }


    }


    // 행과 열
    public static boolean rowCol(int n , int col , int row){
        boolean is=true;
        for(int i=1; i<=9; i++){
            if(map[i][col]==n || map[row][i]==n){
                is=false;
                break;
            }
        }
        return is;
    }
    //9개 칸 겹치는지 확인.
    public static boolean check(int n,int row ,int col){
        boolean is=true;
        row= (row+1)*3;
        col= (col+1)*3;
        for(int i=row-2; i<=row; i++){
            for(int j=col-2; j<=col; j++){
                if(map[i][j]==n){
                    is=false;
                    break;
                }
            }
        }
        return is;
    }

}

//위의 코드와 시간과 로직이 큰차이 없이 똑같지만, 코드의 길이에선 차이가 크다.
//여기선 row, col의 제한내용을 구하는 함수를 하나로 묶었다. 차피 고정된 row,col이외의 값을 
//1-9로 돌면서 같은 수가 겹치는지 확인되기 때문이다.
//또한 full함수를 없앴는데, 차피 depth==size로 return이 된다는 의미는 판이 꽉차서 
//해당 영역까지 온 것이기 때문이다. 따라서, 꽉찬 경우 find를 바꿔 판이 찼다는 의미를 전달한다.