[백준] 2580번 스도쿠 (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++){
            st=new StringTokenizer(br.readLine());
            for(int j=1; j<=9; j++) {
                map[i][j]=Integer.valueOf(st.nextToken());
                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;
    }

}


//사실 아래 포스트와 똑같은 문제이다. 단지 입출력에서 무엇을 받을지의 차이이고, 스페셜 저지이므로,
//아무 스도쿠 배열 값이나 상관없다. 
//아래에선 사전 순으로 제일 앞서는 값을 구하라 했는데 여기선 상관 없으므로 밑에 정답또한 정답이란 것이다.
//그럼 이는 무슨 차이인가.
//사전 순으로 앞서는 스도쿠를 구하려면, 작은 수가 맨위, 맨 왼쪽에 가까워야 한다. 
//바꿔말하면, 백트래킹을 할 때 빈칸에 작은 수 부터 채워가야 한다는 것이다.
//이렇게 채울때 꽉차면 작은 수 부터 채웠으므로 사전 순으로 젤 앞서는 스도쿠 배열이 될 것이다.
//하지만 이 문제는 그런 조건이 없다. 큰 수부터 채우든 중간 수 부터 채우든 상관없이 
//어떻게든 답만 구하면 된다는 것이다.