[백준] 2580 스도쿠

문제 출처: www.acmicpc.net/problem/2580

2580번: 스도쿠

: 스도쿠의 답을 출력하는게 문제이다.

: 스도쿠의 답이 되기 위해서는 행과 열에 중복된 숫자가 없어야 하고 0행0열부터 시작했을 때 3x3행렬안에도 중복된 값이 있어서는 안된다.

: 따라서 각각의 경우마다 중복체크를 할 수 있는 함수를 별도로 만들어준다.

: 비어있던 칸들을 미리 리스트로 만든 후 그 리스트를 재귀적으로 접근하여 위의 3가지 경우 모두 중복되지 않으면 해당 숫자를 집어넣고 다음 비어있는 칸으로 이동할 수 있도록 한다.

: 만약 비어있던 칸들을 모두 채우는 경우가 바로 답이 되기 때문에 이 경우에 답을 출력하고 시스템을 종료한다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int[][] sudoku = new int[9][9];
	static ArrayList<Point> list = new ArrayList<>();
	static class Point{
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}
		
	}
	public static void main(String[] args) throws IOException {
		for(int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 9; j++) {
				sudoku[i][j] = Integer.parseInt(st.nextToken());
				if(sudoku[i][j] == 0) list.add(new Point(i, j));
			}
		}
		setNumber(0);
	
		
	
	}
	private static void setNumber(int idx) {
		if(idx == list.size()) {
			for(int i = 0; i < 9; i++) {
				for(int j = 0; j < 9; j++) {
					System.out.print(sudoku[i][j] + " ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		int r = list.get(idx).r;
		int c = list.get(idx).c;
//		System.out.println(idx);
		for(int i = 1; i < 10; i++) {
			sudoku[r][c] = i;
			// 가로줄 확인			
			// 세로줄 확인
			// 정사각형 확인
			if(checkRow(r) && checkCol(c) && checkBox(r, c)) {
				setNumber(idx+1);
			}
		}
		sudoku[r][c] = 0;
		
	}
	static int[] dr = {0, 1, 2};
	private static boolean checkBox(int r, int c) {
		int sr = r/3;
		int sc = c/3;
		sr *= 3;
		sc *= 3;
		boolean[] v = new boolean[10];
		for(int i = 0; i < 3; i++) {
			int nr = sr+dr[i];
			for(int j = 0; j < 3; j++) {
				int nc = sc + dr[j];
				if(sudoku[nr][nc] != 0 && v[sudoku[nr][nc]]) return false;
				v[sudoku[nr][nc]] = true;
				
			}
		}
		return true;
	}
	private static boolean checkCol(int c) {
		boolean[] v = new boolean[10];
		for(int r = 0; r < 9; r++) {
			if(sudoku[r][c] != 0 && v[sudoku[r][c]]) return false;
			v[sudoku[r][c]] = true;
		}
		return true;
	}
	// 가로줄 확인
	private static boolean checkRow(int r) {
		boolean[] v = new boolean[10];
		for(int c = 0; c < 9; c++) {
			if(sudoku[r][c] != 0 && v[sudoku[r][c]]) return false;
			v[sudoku[r][c]] = true;
		}
		return true;
	}
}