[백준 2239] 스도쿠 / 자바 / dfs(백트래킹)

#문제         

레벨: G4 
알고리즘: dfs(백트래킹)
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

해당 자리에 숫자를 놓으려면 해당 열, 해당 행, 해당 박스 안에 같은 숫자가 있으면 안된다. 이것들을 검사하는 코드를 구현하고 백트래킹을 통해서 숫자를 채워넣으면 된다.

dfs 코드는 아래와 같이 방문한다. 

------------------------->       1 번째 행
------------------------->       2 번째 행
------------------------->       3 번째 행
------------------------->       4 번째 행
------------------------->       5 번째 행
------------------------->       6 번째 행
------------------------->       7 번째 행
------------------------->       8 번째 행
------------------------->       9 번째 행

최악의 시간복잡도를 계산해보자면 모든 칸이 빈칸이라 1 ~ 9 까지 다 넣어보는 것이다. 그렇게 된다면 O(9^81)로 무조건 시간제한에서 아웃이다. 그러나 문제에서 이정도 최악의 상황은 안 주나보다. 그리고 백트래킹으로 인해 예상 시간복잡도보다 훨씬 단축되긴 할 것이다. 

---

#풀이 코드      

import java.io.*;

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

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

        // 스도쿠 보드 입력 받기
        for (int i = 0; i < 9; i++) {
            String line = br.readLine();
            for (int j = 0; j < 9; j++) {
                board[i][j] = line.charAt(j) - '0';
            }
        }

        solve(0, 0);
    }

    private static boolean solve(int row, int col) {
        if (col == 9) {
            row++;
            col = 0;
        }

        if (row == 9) {
            printBoard();
            return true;
        }

        if (board[row][col] != 0) {
            return solve(row, col + 1);
        }

        for (int num = 1; num <= 9; num++) {
            if (isValid(row, col, num)) {
                board[row][col] = num;
                if (solve(row, col + 1)) {
                    return true;
                }
                board[row][col] = 0;
            }
        }

        return false;
    }

    private static boolean isValid(int row, int col, int num) {
        // 행 확인
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) return false;
        }

        // 열 확인
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) return false;
        }

        // 3x3 박스 확인
        int boxRow = row - row % 3;
        int boxCol = col - col % 3;
        for (int i = boxRow; i < boxRow + 3; i++) {
            for (int j = boxCol; j < boxCol + 3; j++) {
                if (board[i][j] == num) return false;
            }
        }

        return true;
    }

    private static void printBoard() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }
}