[백준] 2580번 : 스도쿠(JAVA)

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

2580번: 스도쿠

---

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 15단계

 

백트래킹의 카테고리에 포함되어 있는 문제이다.

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

public class Question_2580 {

	public static final int size = 9;
	public static int[][] arr;
	
	public static List<int[]> list;
	public static boolean isEnd;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = null;
		
		arr = new int[size][size];
		list = new ArrayList<>();
		
		for(int i = 0; i < size; i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j = 0; j < size; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				
				if(arr[i][j] == 0) {
					list.add(new int[] {i, j}); 
				}
			}	
		}
			backtracking(0, 0);
	}
	
	public static void backtracking(int idx, int cnt) {
		if(isEnd)
			return;
		
		if(cnt == list.size()) {
			isEnd = true;
			print();
			return;
		}
		
		if(idx >= list.size())
			return;
		
		int y = list.get(idx)[0];
		int x = list.get(idx)[1];
		
		for(int i = 1; i <= 9; i++) {
			if(isAble(y, x, i)) {
				arr[y][x] = i;
				backtracking(idx+1, cnt+1);
				arr[y][x] = 0;
			}
		}
		
	}
	
	public static boolean isAble(int y, int x, int v) {
		for(int i = 0; i < size; i++) {
			if(arr[y][i] == v)
				return false;
			if(arr[i][x] == v)
				return false;
		}
		
		int y_s = y/3 * 3;
		int x_s = x/3 * 3;
		
		for(int i = y_s; i < y_s+3; i++) {
			for(int j = x_s; j < x_s+3; j++) {
				if(arr[i][j] == v)
					return false;
			}
		}
		
		return true;
	}
	
	public static void print() {
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				sb.append(arr[i][j] + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
		
	}
}