/ BOJ

BOJ_2239_스도쿠_JAVA

문제 : 스도쿠

링크 : BOJ_2239_스도쿠

접근 방식

스도쿠 규칙에 맞게 수를 채워넣어야 하는 문제이다.

조건으로써 완성되는 스도쿠의 답이 여러 개 있다면 사전 순으로 앞서는 스도쿠 완성 결과를 출력해야한다.

소스 코드

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

public class BOJ_2239_스도쿠 {
	static char[][] sudoku;
	static String answer = "";

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		sudoku = new char[9][9];

		for (int i = 0; i < 9; i++) {
			sudoku[i] = in.readLine().toCharArray();
		}

		dfs(0, 0);

		System.out.println(answer);
	}

	public static void dfs(int x, int y) {

		if (y == 9) {
			StringBuilder sb = new StringBuilder();
			String[] str = answer.split("\n");
			for(int i=0;i<9;i++) {
				sb.append(sudoku[x][i]);
			}

			if(answer != "" && str[x].compareTo(sb.toString()) < 0 ) {
				return;
			}
			dfs(x + 1, 0);
			return;
		}

		if (x == 9) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(sudoku[i][j]);
				}
				sb.append("\n");
			}
			if (answer.compareTo(sb.toString()) < 0) {
				answer = sb.toString();
			}
			return;
		}

		if (sudoku[x][y] == '0') {
			for (int i = 1; i <= 9; i++) {
				if (check(x, y, i + '0')) {
					sudoku[x][y] = (char) (i + '0');
					dfs(x,y+1);
				}
			}
			sudoku[x][y] = '0';
			return;
		}

		dfs(x, y + 1);

	}

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

		// 같은 열
		for (int i = 0; i < 9; i++) {
			if (sudoku[x][i] == value) {
				return false;
			}
		}

		// 같은 행
		for (int i = 0; i < 9; i++) {
			if (sudoku[i][y] == value) {
				return false;
			}
		}

		int xx = (x / 3) * 3;
		int yy = (y / 3) * 3;

		for (int i = xx; i < xx + 3; i++) {
			for (int j = yy; j < yy + 3; j++) {
				if (sudoku[i][j] == value) {
					return false;
				}
			}
		}
		return true;

	}
}

dfs를 통해 탐색하며 스도쿠 조건을 계속해서 체크하는 부분을 구현하는 것이 어려웠던 것 같다.