백준 2239번 스도쿠 (JAVA)

백준 2239번 스도쿠 (JAVA)

문제

난이도

• 골드 4

알고리즘 분류

• 구현
• 백트래킹

풀이

0인 경우, 숫자 1 ~ 9까지 대입

1 ~ 9 까지의 숫자중 스도쿠의 조건을 만족하는 경우(3*3, 행, 열) 해당 위치에 숫자를 대입하고 다음 단계 탐색(방문)

방문 여부를 초기화(0으로) 한 후 대입 가능한 숫자를 계속 탐색

81자리 까지 끝까지 탐색한 경우, 최초의 정답을 반환해야한다.(사전순)

처음 탐색 종료 조건(81자리 모두 탐색)을 만족하면 각 단계를 탐색하기 전에 최최 탐색 완료 여부를 확인

코드

import java.io.*;

public class Main {

    static int arr[][];
    static boolean check;

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

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        arr = new int[9][9];

        for (int i = 0; i < 9; i++) {
            char[] split = in.readLine().toCharArray();
            for (int j = 0; j < 9; j++) {
                arr[i][j] = split[j] - '0';
            }
        }

        // 0, 1, 2, 3, 4, 5, 6, 7, 8
        check = false;
        solve(0);

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(arr[i][j]);
            }
            sb.append("\n");
        }

        out.write(sb.toString());
        out.close();
    }

    private static void solve(int depth) {
        if (depth == 81) {
            check = true;
            return;
        }

        int row = depth / 9;
        int col = depth % 9;

        if (arr[row][col] != 0) {
            solve(depth + 1);
        } else {
            for (int num = 1; num <= 9; num++) {
                if (checkBox(row, col, num) && checkRow(row, num) && checkCol(col, num)) {
                    arr[row][col] = num;
                    solve(depth + 1);
                    if (check) {
                        return;
                    }
                    arr[row][col] = 0;
                }
            }
        }
    }

    private static boolean checkCol(int col, int num) {
        for (int row = 0; row < 9; row++) {
            if (arr[row][col] == num) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkRow(int row, int num) {
        for (int col = 0; col < 9; col++) {
            if (arr[row][col] == num) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkBox(int x, int y, int num) {
        int row = (x / 3) * 3;
        int col = (y / 3) * 3;

        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if (arr[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}