[ 백준/Java ] 2239. 스도쿠

백준 링크 : https://www.acmicpc.net/problem/2239

 

🌱 [ 문제 요약 ]

위는 완성된 스도쿠의 예시이다.

스도쿠의 규칙은 각 영역에 겹치는 수 없이 1 ~ 9 숫자를 채우는 것이다. 영역은 다음과 같다.

• 3 * 3 영역
• 행 / 열

완성 되지 않은 스도쿠 ( 채워진 부분은 숫자, 안 채워진 부분은 0 )가 주어질 때 스도쿠를 완성 하여 출력 하라.

(단. 정답이 여러개인 경우 사전순으로 가장 앞서는 것을 출력 하라. )

 

🌱 [ 알고리즘 선택 ]

스도쿠의 조건을 만족 하기 위한 탐색이 필요 합니다.

스도쿠를 완성 하면 탐색을 종료 하기 때문에 백트래킹 입니다.

 

🔥 [ 구현 방법 ]

1. 탐색을 위해 빈셀을 모두 찾습니다.

2. 빈셀에 숫자를 선택 하고 조건( 행, 열, 섹션 )을 검사 합니다.

3. 조건 충족시 셀에 숫자를 변경 하고 깊이 탐색을 이어 갑니다.

4. 빈셀 수 만큼 모두 탐색 하였으면 종료 합니다.

---

[ 탐색 ]

• 탈출 조건 : 빈셀들을 모두 채웠을 때 ( 재귀의 깊이 )

[ 재귀 조건 ]

• 빈셀에 임의의 수를 넣을 때 이미 같은 수가 행에 있는가?
• 빈셀에 임의의 수를 넣을 때 이미 같은 수가 열에 있는가?
• 빈셀에 임의의 수를 넣을 때 이미 같은 수가 영역에 있는가? 

static void dfs(int depth) {
        if (depth == blanks.size()) {
            escape = true;
            return;
        }

        Blank blank = blanks.get(depth);
        int row = blank.row;
        int col = blank.col;

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

            if (isNotDuplicationInRow(row, num) &&
                    isNotDuplicationInCol(col, num) &&
                    isNotDuplicationInSection(row, col, num)) {

                sudoku[row][col] = num;
                dfs(depth + 1);

                if (escape) return;
                sudoku[row][col] = 0;
            }
        }
    }

---

[ 섹션 검사 방법 ]

• 그림처럼 열을 기준으로 섹션을 나눌수 있습니다. 
• 섹션의 범위는 섹션의 시작점 ~ 시작점 + 2 까지 입니다.
• 4번째 열에 놓는다면 범위는 3 ~ 5 입니다. 
• 행도 마찬가지로 구할수 있습니다.

static boolean isNotDuplicationInSection(int startRow, int startCol, int num) {
        int rowSection = startRow / 3 * 3;
        int colSection = startCol / 3 * 3;

        for (int row = rowSection; row < rowSection + 3; row++) {
            for (int col = colSection; col < colSection + 3; col++) {
                if (sudoku[row][col] == num) return false;
            }
        }
        return true;
    }

 

---

[ 전체 코드 ]

public class Main {
    static final int SUDOKU_ROW_SIZE = 9;
    static List<Blank> blanks;
    static int[][] sudoku;
    static boolean escape = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sudoku = new int[SUDOKU_ROW_SIZE][];

        // 입력받기
        for (int i = 0; i < SUDOKU_ROW_SIZE; i++) {
            sudoku[i] = Stream.of(br.readLine().split("")).mapToInt(string -> string.charAt(0) - '0').toArray();
        }

        // 빈칸 개수 찾기
        blanks = new ArrayList<>();
        for (int row = 0; row < sudoku.length; row++) {
            for (int col = 0; col < sudoku[0].length; col++) {
                if (sudoku[row][col] == 0) {
                    blanks.add(new Blank(row, col));
                }
            }
        }

        dfs(0);
        printSudoku();
    }

    static void dfs(int depth) {
        if (depth == blanks.size()) {
            escape = true;
            return;
        }

        Blank blank = blanks.get(depth);
        int row = blank.row;
        int col = blank.col;

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

            if (isNotDuplicationInRow(row, num) &&
                    isNotDuplicationInCol(col, num) &&
                    isNotDuplicationInSection(row, col, num)) {

                sudoku[row][col] = num;
                dfs(depth + 1);

                if (escape) return;
                sudoku[row][col] = 0;
            }
        }
    }

    static boolean isNotDuplicationInRow(int row, int num) {
        for (int col = 0; col < sudoku[0].length; col++) {
            if (sudoku[row][col] == num) return false;
        }
        return true;
    }

    static boolean isNotDuplicationInCol(int col, int num) {
        for (int row = 0; row < sudoku.length; row++) {
            if (sudoku[row][col] == num) return false;
        }
        return true;
    }

    static boolean isNotDuplicationInSection(int startRow, int startCol, int num) {
        int rowSection = startRow / 3 * 3;
        int colSection = startCol / 3 * 3;

        for (int row = rowSection; row < rowSection + 3; row++) {
            for (int col = colSection; col < colSection + 3; col++) {
                if (sudoku[row][col] == num) return false;
            }
        }
        return true;
    }

    static void printSudoku() {
        StringBuilder sb = new StringBuilder();
        for (int row = 0; row < sudoku.length; row++) {
            for (int col = 0; col < sudoku[0].length; col++) {
                sb.append(sudoku[row][col]);
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

    static class Blank {
        private int row;
        private int col;

        public Blank(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}