백준 2580 스도쿠 (JAVA 자바 풀이)

백준 2580 스도쿠 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

 

⚔ 입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

 

📣 출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

틀리기 쉬운 부분은 3가지 조건을 만족하지 못했을 때 (= 이전 값을 잘못 찾아서 더 진행이 안될때) 0으로 초기화해주고 다시 이전 것을 찾아야 한다는 부분이다. 

 

이것을 놓쳐서 계속 틀렸다. 

 

 

 

💡 코드 구현

 

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

public class Main {

	private static int[][] sudoku;
	private static boolean finish;
	private static ArrayList<Integer> blankX;
	private static ArrayList<Integer> blankY;

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

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

		sudoku = new int[9][9];
		blankX = new ArrayList<>();
		blankY = new ArrayList<>();
		for (int i = 0; i < 9; i++) {
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			for (int j = 0; j < 9; j++) {
				int number = Integer.parseInt(stringTokenizer.nextToken());
				sudoku[i][j] = number;

				if (number == 0) {
					blankX.add(i);
					blankY.add(j);
				}
			}
		}

		dfs(0);

		StringBuilder stringBuilder = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(sudoku[i][j] + " ");
			}
			System.out.println();
		}

	}

	private static void dfs(int depth) {
		if (depth == blankX.size()) {
			finish = true;
			return;
		}

		int blankNumberX = blankX.get(depth);
		int blankNumberY = blankY.get(depth);

		for (int i = 1; i <= 9; i++) {

			if (!isSameNumberAtRow(blankNumberX, i) && !isSameNumberAtCol(blankNumberY, i) && !isSameNumberAt3x3(blankNumberX, blankNumberY, i)) {
				sudoku[blankNumberX][blankNumberY] = i;
				dfs(depth + 1);
			}

			if (finish) {
				return;
			}
		}
		sudoku[blankNumberX][blankNumberY] = 0;
	}

	private static boolean isSameNumberAtRow(int x, int checkNumber) {

		for (int i = 0; i < 9; i++) {
			if (sudoku[x][i] == checkNumber) {
				return true;
			}
		}
		return false;
	}

	private static boolean isSameNumberAtCol(int y, int checkNumber) {
		for (int i = 0; i < 9; i++) {
			if (sudoku[i][y] == checkNumber) {
				return true;
			}
		}
		return false;
	}

	private static boolean isSameNumberAt3x3(int x, int y, int checkNumber) {
		int boxX = (x / 3) * 3;
		int boxY = (y / 3) * 3;

		for (int i = boxX; i < boxX + 3; i++) {
			for (int j = boxY; j < boxY + 3; j++) {
				if (i == x && j == y) {
					continue;
				}

				if (sudoku[i][j] == checkNumber) {
					return true;
				}
			}

		}
		return false;
	}
}