백준 2580. 스도쿠

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

 

나의 풀이

백트래킹 알고리즘을 통해서 풀어 보았다.(내 실제 스도쿠 풀이도 이와 비슷한 것 같다. 첫 번째 가능성으로 쭉 풀고, 두 번째 가능성으로 쭉 풀고, 안되면 커트하고, 트리를 만들어가듯이 푸는 것)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int[][] sudokuField = new int[9][9];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// 스도쿠 배열 초기화
		for (int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				sudokuField[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solve(sudokuField, 0, 0);
		for (int[] item : sudokuField) {
			for (int elem : item) {
				System.out.print(elem + " ");
			}
			System.out.println();
		}
		bw.close();
		br.close();
	}

	static boolean solve(int[][] sudokuField, int row, int col) {
		// 종료 조건
		if (row == 9) {
			return true;
		}

		int nextRow = (col == 8) ? row + 1 : row;
		int nextCol = (col == 8) ? 0 : col + 1;

		if (sudokuField[row][col] != 0) {
			return solve(sudokuField, nextRow, nextCol);
		}

		for (int i = 1; i <= 9; i++) {
			if (isValid(sudokuField, row, col, i)) {
				sudokuField[row][col] = i;
				if (solve(sudokuField, nextRow, nextCol)) {
					return true;
				}
				sudokuField[row][col] = 0;
			}
		}
		return false;
	}

	static boolean isValid(int[][] sudokuField, int row, int col, int value) {
		// 가로줄 확인
		for (int i = 0; i < 9; i++) {
			if (sudokuField[row][i] == value) {
				return false;
			}
		}
		// 세로줄 확인
		for (int i = 0; i < 9; i++) {
			if (sudokuField[i][col] == value) {
				return false;
			}
		}
		// 9칸 확인
		int colType = (col / 3) * 3;
		int rowType = (row / 3) * 3;

		for (int i = rowType; i < rowType + 3; i++) {
			for (int j = colType; j < colType + 3; j++) {
				if (sudokuField[i][j] == value) {
					return false;
				}
			}
		}
		return true;
	}

}