[백준] 2239번 : 스도쿠

문제

2239번: 스도쿠

 

접근 방식

스도쿠의 빈칸을 채우는 문제다.

 

특별한 규칙은 없기 때문에 백트래킹으로 매번 행과 열, 3*3칸을 확인해 주며

가능한 숫자들을 모두 시도해보아야 한다.

 

문제의 설명이 조금 헷갈렸는데 81 자리의 수가 제일 작은 경우라는 말이

81번째 칸을 말하는 게 아니라 9*9칸을 일렬로 늘어놨을 때

나오는 81자리 수를 말하는 것이기 때문에 백트래킹 자체를

1 ~ 9까지의 수를 오름차순으로 대입하다 보면 처음 나오는 결과가

가장 작은 수이기 때문에 그 이후는 탐색하지 않고 탐색을 끝내면 된다.

 

수들을 선택할 때마다 현재 행과 열, 구역에 해당 수의 사용여부를 기록하면

매번 행, 열, 구역을 확인하는 것보다 편리하게 백트래킹을 할 수 있다.

 

 

풀이

public class Main {

	static int tx = 0, ty = 0, cnt = 81;
	static int[][] map = new int[9][9];
	static boolean[][] isUsedX = new boolean[9][10];
	static boolean[][] isUsedY = new boolean[9][10];
	static boolean[][] isUsedTT = new boolean[10][10];
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input;

		for (int i = 0; i < 9; i++) {
			input = br.readLine().split("");
			for (int j = 0; j < 9; j++) {
				int num = Integer.parseInt(input[j]);
				map[i][j] = num;
				if (num != 0) {
					cnt--;
					isUsedX[i][num] = true;
					isUsedY[j][num] = true;
					isUsedTT[getTT(i, j)][num] = true;
				} else {
					tx = i;
					ty = j;
				}
			}
		}

		solve(0, 0);

		System.out.println(sb);
	}

	static boolean solve(int x, int y) {
		if (x == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(map[i][j]);
				}
				sb.append("\n");
			}
			return true;
		}

		if (map[x][y] != 0) {
			if (y == 8) {
				if (solve(x + 1, 0)) return true;
			}
			else {
				if(solve(x, y + 1)) return true;
			}
		} else {
			for (int i = 1; i <= 9; i++) {
				int tt = getTT(x, y);
				if (isUsedX[x][i] || isUsedY[y][i] || isUsedTT[tt][i]) {
					continue;
				}

				isUsedX[x][i] = true;
				isUsedY[y][i] = true;
				isUsedTT[tt][i] = true;
				map[x][y] = i;

				if (y == 8) {
					if (solve(x + 1, 0)) return true;
				}
				else {
					if(solve(x, y + 1)) return true;
				}

				map[x][y] = 0;
				isUsedX[x][i] = false;
				isUsedY[y][i] = false;
				isUsedTT[tt][i] = false;
			}
		}

		return false;
	}

	static int getTT(int i, int j) {
		if (i < 3) {
			if (j < 3) return 1;
			else if (j < 6) return 2;
			else return 3;
		} else if (i < 6) {
			if (j < 3) return 4;
			else if (j < 6) return 5;
			else return 6;
		} else {
			if (j < 3) return 7;
			else if (j < 6) return 8;
			else return 9;
		}
	}
}