백준/2580/Java - 스도쿠

문제

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

2580번: 스도쿠

---

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

class Zero{
	int x;
	int y;
	Zero(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static int zCount;
	static int[][] arr = new int[9][9];
	static boolean[] visit = new boolean[26];
	static ArrayList<Zero> zList;
	static StringBuilder sb = new StringBuilder();

;	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		zList = new ArrayList<>();
		
		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) zList.add(new Zero(i, j));
			}
		}
		zCount = zList.size();
		dfs(0);

	}

	public static void dfs(int depth) {
		if(depth == zCount) {
			print();
			System.exit(0);
			return;
		}
		int x = zList.get(depth).x;
		int y = zList.get(depth).y;
		for(int j=1; j<=9; j++) {
			arr[x][y] = j;
			if(sudoku(x,y)) dfs(depth+1);
			arr[x][y] = 0;
		}
	}
	public static boolean sudoku(int x, int y) {
		for(int i=0; i<9; i++) {
			if(arr[x][i] == arr[x][y] && i != y) {
				return false; //세로 체크 
			}
			if(arr[i][y] == arr[x][y] && i != x) {
				return false; //가로 체크 
			}
		}
		int sx = 0, ex = 0, sy =0, ey = 0;

		switch(x%3) {
			case 0: sx = x; ex=x+2;  break;
			case 1: sx = x-1; ex=x+1; break;
			case 2: sx = x-2; ex=x; break;
		}

		switch(y%3) {
			case 0: sy = y; ey=y+2;  break;
			case 1: sy = y-1; ey=y+1; break;
			case 2: sy = y-2; ey=y; break;
		}
		
		for(int i=sx; i<=ex; i++) {
			for(int j=sy; j<=ey; j++) {
				if(arr[i][j] == arr[x][y] && i != x && j != y) {
					return false;
				}
			}
		}
		return true;
	}
	public static void print() {
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				sb.append(arr[i][j] + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}