[알고리즘][X] 스도쿠

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

2239번: 스도쿠

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

public class Main {
	static final int MAX_N = 9 * 9;
	static boolean[][][] section;
	static boolean[][] row;
	static boolean[][] col;
	static int[][] zeros;
	static int[][] map;
	static int zeroCount = 0;
	static boolean flag;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		section = new boolean[3][3][10];
		row = new boolean[10][10];
		col = new boolean[10][10];
		zeros = new int[MAX_N][];
		map = new int[10][10];
		
		for (int i = 1; i <= 9; i++) {
			String line = br.readLine();
			for (int j = 1; j <= 9; j++) {
				int n = line.charAt(j-1) - '0';
				if (n == 0) {
					zeros[zeroCount++] = new int[] {i, j};
					continue;
				}
				section[(i-1) / 3][(j-1) / 3][n] = true;
				row[i][n] = true;
				col[j][n] = true;
				map[i][j] = n;
			}
		}
		
		dfs(0);
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				sb.append(map[i][j]);
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	private static void dfs(int depth) {
		if (depth == zeroCount) {
			flag = true;
			return;
		}
		
		int[] zero = zeros[depth];
		int r = zero[0];
		int c = zero[1];
		for (int i = 1; i <= 9; i++) {
			if (row[r][i] == true || col[c][i] == true || section[(r-1)/3][(c-1)/3][i] == true) {
				continue;
			}
			row[r][i] = true;
			col[c][i] = true;
			section[(r-1)/3][(c-1)/3][i] = true;
			map[r][c] = i;
			dfs(depth+1);
			if (flag) return;
			row[r][i] = false;
			col[c][i] = false;
			section[(r-1)/3][(c-1)/3][i] = false;
			map[r][c] = 0;

		}
	}
}

나의 풀이

- -1/3 = 0이다. -3/3=-1이다.

- 여러개가 성공일 수 있기 때문에 일단 하나라도 완성이 되면 재귀를 끝내주어야 한다. 그러지 않아서 시간 초과가 났다.

- 답은 하나라는데 사전순이다. 그렇다면 zeros를 넣은 순서대로 재귀를 들어가주면 정답이 된다. 조심하자!!