[BaekJoon] 2239 스도쿠 (Java)

1.  문제 링크

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

2.  문제

요약

• 스도쿠는 9 x 9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3 x 3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우는 숫자 퍼즐입니다.
• 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 문제입니다.
• 입력: 9개의 줄에 9개의 숫자로 보드가 주어집니다. 아직 숫자가 채워지지 않은 칸에는 0이 주어집니다.
• 출력: 9개의 줄에 9개의 숫자로 답을 출력합니다. 답이 여러 개라면 그 중 사전식으로 앞서는 것을 출력합니다. 즉, 81자리의 수가 제일 작은 경우를 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static final int SIZE = 9;
	static int[][] board;
	static LinkedList<int[]> zeros;
	static void input() {
		Reader scanner = new Reader();
		board = new int[SIZE][SIZE];
		zeros = new LinkedList<>();
		for(int row = 0; row < SIZE; row++) {
			String info = scanner.nextLine();
			for(int col = 0; col < SIZE; col++) {				
				board[row][col] = info.charAt(col) - '0';
				if(board[row][col] == 0) zeros.add(new int[] {row, col});
			}
		}
	}
	
	static void solution() {
		rec_func(0, zeros.size());
	}
	
	static void rec_func(int idx, int size) {
		if(size == 0) {
			for(int row = 0; row < SIZE; row++) {
				for(int col = 0; col < SIZE; col++) sb.append(board[row][col]);
				sb.append('\n');
			}
			System.out.println(sb);
			System.exit(0);
		}
		int[] cur = zeros.get(idx);
		int startRow = (cur[0] / 3) * 3, startCol = (cur[1] / 3) * 3;
		for(int num = 1; num <= 9; num++) {
			board[cur[0]][cur[1]] = num;
			if(checkRow(cur) && checkCol(cur) && checkBoard(new int[] {startRow, startCol})) {					
				rec_func(idx + 1, size - 1);
			}
			board[cur[0]][cur[1]] = 0;
		}
	}
	
	static boolean checkRow(int[] position) {
		boolean[] nums = new boolean[10];
		for(int col = 0; col < SIZE; col++) {
			if(board[position[0]][col] != 0) {
				if(nums[board[position[0]][col]]) return false;
				nums[board[position[0]][col]] = true;
			}
		}
		return true;
	}
	
	static boolean checkCol(int[] position) {
		boolean[] nums = new boolean[10];
		for(int row = 0; row < SIZE; row++) {
			if(board[row][position[1]] != 0) {
				if(nums[board[row][position[1]]]) return false;
				nums[board[row][position[1]]] = true;
			}
		}
		return true;
	}
	
	static boolean checkBoard(int[] position) {
		boolean[] nums = new boolean[10];
		for(int row = 0; row < 3; row++) {
			for(int col = 0; col < 3; col++) {
				if(board[position[0] + row][position[1] + col] != 0) {
					if(nums[board[position[0] + row][position[1] + col]]) return false;
					nums[board[position[0] + row][position[1] + col]] = true;
				}
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}