[JAVA] 백준 2580번- 스도쿠

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

2580번: 스도쿠

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    static int[][] arr = new int[9][9];
    static boolean[][] check_row = new boolean[9][9]; // x행에 숫자 y가 있으면 true
    static boolean[][] check_col = new boolean[9][9]; // x열에 숫자 y가 있으면 true
    static boolean[][] check_square = new boolean[9][9]; // x번째 사각형에 숫자 y가 있으면 true

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i=0; i<9; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<9; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]!= 0){
                    check_row[i][arr[i][j]-1] = true;
                    check_col[j][arr[i][j]-1] = true;
                    check_square[box(i, j)][arr[i][j]-1] = true;
                }
            }
        }
        dfs(0, 0);

        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }
    static int box(int i, int j){ // 몇번째 박스인지
        return (i/3) * 3 + (j/3);
    }

    static boolean dfs(int x, int y){
       if(x==9){ // 모든 칸을 다 채우면
           return true;
       }

       if(arr[x][y] != 0){ // 비어있는 칸이 아니면 다음 열 탐색
           return dfs(x+(y+1)/9, (y+1)%9);

       }

       for(int i=0; i<9; i++){
           if(check_row[x][i] || check_col[y][i] || check_square[box(x, y)][i]) continue; // 넣을 수 없는 값
           arr[x][y] = i+1;
           check_row[x][i] = check_col[y][i] = check_square[box(x, y)][i] = true;
           if(dfs(x+(y+1)/9, (y+1)%9)) return true; // 다음 열 탐색, 답을 찾으면 바로 리턴
           arr[x][y] = 0;
           check_row[x][i] = check_col[y][i] = check_square[box(x, y)][i] = false;
       }
       return false; // 백트래킹 실패
    }
}