[Java] BOJ2239_스도쿠

www.acmicpc.net/problem/2239

2239번: 스도쿠

---

모든 경우를 다 따지면 최악의 경우 9^81 횟수가 나온다. 따라서 가지치기를 해줘야 하는 문제이다.

매번 반복문을 돌아서 값이 0인것을 찾기보다는 0인 애들의 index를 리스트에 담아두고 list로 반복문을 돌리는 게 유리하다.

"답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다." 출력 조건에 맞추기 위해 스도쿠가 처음 완성되는 시점에 함수를 빠져나오도록 했다. 1부터 채우기 때문에 처음 완성되는 것이 사전식으로 가장 앞선다.

가지치기를 위한 check함수는 전체 배열을 검사하기보다는 값을 삽입한 index를 가지고 가서 그 index가 속한 행과 열, 그리고 사각형을 검사하는 것이 유리하다.

 

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


public class Main {

	static int[][] arr = new int[9][9];
	static ArrayList<int[]> list = new ArrayList<>();
	static boolean flag = false;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 9; i++) {
			String s = br.readLine();
			for (int j = 0; j < 9; j++) {
				arr[i][j] = s.charAt(j) - '0';
				if(arr[i][j] == 0) list.add(new int[] {i, j});
			}
		}
		
		sdoku(list.size(), 0, -1, -1);
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(arr[i][j]);
			}
			System.out.println();
		}
	}

	public static void sdoku(int len, int cnt, int r, int c) {
		if(flag) return;
		if(cnt != 0 && check(r, c)) return;
		if(cnt == len) {
			flag = true;
			return;
		}
		int[] cur = list.get(cnt);
		for (int i = 1; i <= 9; i++) {
			arr[cur[0]][cur[1]] = i;
			sdoku(len, cnt+1, cur[0], cur[1]);
			if(flag) break;
			arr[cur[0]][cur[1]] = 0;
		}
	}

	private static boolean check(int r, int c) {
		boolean[] row = new boolean[10];
		boolean[] col = new boolean[10];
		boolean[] square = new boolean[10];
		for (int i = 0; i < 9; i++) {
			if(arr[r][i] > 0) {
				if(row[arr[r][i]]) return true;
				else row[arr[r][i]] = true;
			}
			if(arr[i][c] > 0) {
				if(col[arr[i][c]]) return true;
				else col[arr[i][c]] = true;
			}
		}
		int sr = 0, sc = 0;
		if(r >= 6) sr = 6;
		else if(r >= 3) sr = 3;
		else if(r >= 0) sr = 0;
		if(c >= 6) sc = 6;
		else if(c >= 3) sc = 3;
		else if(c >= 0) sc = 0;
		
		for (int i = sr; i < sr+3; i++) {
			for (int j = sc; j < sc+3; j++) {
				if(arr[i][j] > 0) {
					if(square[arr[i][j]]) return true;
					else square[arr[i][j]] = true;
				}
			}
		}
		
		return false;
	}
}