백준2239 - 스도쿠 java

package a0406;

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

/*
 2차원배열에서 0인곳 dfs돌면서 조건 만족하는 수 완탐?
 
 조건 1) 가로 2) 세로 3) 범위사각형 
 
 */
public class 백준2239_스도쿠 {

	static int[][] arr = new int[9][9];
	static ArrayList<int[]> zerolist = new ArrayList<>();
	static int allflag = 0;
	
	static void dfs(int cnt) {
		//System.out.println(cnt);
		//print();
		if(allflag==1)return;
		
		if(cnt==zerolist.size()) {
			for(int i=0; i<9; i++) {
				for(int j=0; j<9; j++) {
					System.out.print(arr[i][j]);
				}
				System.out.println();
			}
			allflag = 1;
			return;
		}
		
		int now[] = zerolist.get(cnt);
		int nowi = now[0];	int nowj = now[1];
		
		for(int i=1; i<=9; i++) {
			if(garosafe(nowi, nowj, i) && serosafe(nowi, nowj, i) && boxsafe(nowi, nowj, i)) {
				arr[nowi][nowj] = i;
				dfs(cnt+1);
				arr[nowi][nowj] = 0;
			}
		}	
	}
	
	static void print() {
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	static boolean garosafe(int i, int j, int num) {
		
		for(int k=0; k<9; k++) {
			if(arr[i][k]==num)return false;
		}
		return true;
	}
	
	static boolean serosafe(int i, int j, int num) {
		for(int k=0; k<9; k++) {
			if(arr[k][j]==num)return false;
		}
		return true;
	}
	
	static boolean boxsafe(int i, int j, int num) {
		
		int serostart = (i/3)*3;
		int garostart = (j/3)*3;
		
		for(int k=serostart; k<serostart+3; k++) {
			for(int l=garostart; l<garostart+3; l++) {
				if(num==arr[k][l])return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for(int i=0; i<9; i++) {
			String st = br.readLine();
			for(int j=0; j<9; j++) {
				arr[i][j] = st.charAt(j)-'0';
				if(arr[i][j]==0)zerolist.add(new int[] {i, j});
			}
		}
		dfs(0);
		
	}
}