[백준] 2239. 스도쿠 (Java)

 

문제

2239번: 스도쿠

 

알고리즘

구현, 백트래킹

 

풀이

앞 쪽에 있는 0부터 1~9 중 가능한 수로 채워나가며 모든 경우의 수를 따져 해결한다.

답이 여러개 있다면 사전순으로 앞서는 것을 출력하라는 조건이 있기 때문에

1부터 9의 오름차순 순서로 값을 넣었을 때 가장 처음 성공하는 경우가 사전순으로 가장 앞서는 경우이다.

 

답이 없는 입력은 주어지지 않으므로

입력에서 0의 개수를 세고, 해당 좌표를 리스트에 저장한다.

 

재귀 호출 함수 안에서는 리스트의 앞에 있는 좌표부터 1~9까지 가능한 수를 채우고 다음 dfs를 재귀 호출한다.

다시 말해 깊이 0의 호출에서는 0번째 0을 채우고, 깊이 1의 호출에서는 1번째 0을 채우는 식이다.

 

리스트의 마지막 좌표의 0까지 채웠다면

즉, dfs의 깊이가 0의 개수와 동일해졌다면 그때의 답이 사전식으로 제일 앞서는 답이므로 출력하고 프로그램을 종료한다.

 

* 만약 불가능한 경우라서 재귀가 반환되면 다른 값으로 바꾸었던 0을 다시 0으로 되돌려야한다.

 

코드

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

public class Main {
	static int[][] board;
	static ArrayList<Pos> zeroList;

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

		board = new int[9][9];
		zeroList = new ArrayList<>();

		for (int i = 0; i < 9; i++) {
			String str = br.readLine();

			for (int j = 0; j < 9; j++) {
				board[i][j] = str.charAt(j) - '0';

				if (board[i][j] == 0)
					zeroList.add(new Pos(i, j));
			}
		}

		dfs(0);
	}

	private static void dfs(int count) {

		if (count == zeroList.size()) {
			print();
			System.exit(0);
		}

		Pos cur = zeroList.get(count);

		for (int i = 1; i <= 9; i++) {
			board[cur.y][cur.x] = i;
			if (check(cur.y, cur.x)) {
				dfs(count + 1);
			}

			board[cur.y][cur.x] = 0;
		}
	}

	private static void print() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sb.append(board[i][j]);
			}
			sb.append("\n");
		}

		System.out.println(sb);
	}

	private static boolean check(int y, int x) {

		// 가로
		int[] count = new int[10];
		for (int i = 0; i < 9; i++) {
			int num = board[y][i];
			if (num != 0 && ++count[num] == 2) {
				return false;
			}
		}

		// 세로
		count = new int[10];
		for (int i = 0; i < 9; i++) {
			int num = board[i][x];
			if (num != 0 && ++count[num] == 2) {
				return false;
			}
		}

		// 사각형
		count = new int[10];
		int ys = y / 3 * 3;
		int xs = x / 3 * 3;

		for (int i = ys; i < ys + 3; i++) {
			for (int j = xs; j < xs + 3; j++) {
				int num = board[i][j];
				if (num != 0 && ++count[num] == 2) {
					return false;
				}
			}
		}

		return true;
	}

	static class Pos {
		int y, x;

		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}

	}
}