백준 2580 스도쿠 (Java, DFS 백트래킹)

문제 설명

스도쿠는 9×9 크기의 보드로 구성되며, 일부 칸에는 1부터 9까지의 숫자가 주어진다. 나머지 빈칸에 1부터 9까지의 숫자를 넣어 각 행, 각 열 그리고 3×3 박스에 중복 없이 숫자가 들어가도록 스도쿠를 완성해야 한다.

---

전체 코드

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 스도쿠 입력 받기
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                board[i][j] = sc.nextInt();

        solution(0, 0); // 스도쿠 풀이 시작

        // 결과 출력
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                System.out.print(board[i][j] + " ");
            System.out.println();
        }
    }

    static boolean solution(int row, int col) {
        // 다음 행으로 이동
        if (col == 9) return solution(row + 1, 0);
        // 마지막 행까지 완료된 경우
        if (row == 9) return true;

        // 이미 채워진 칸은 건너뛴다
        if (board[row][col] != 0) return solution(row, col + 1);

        // 1부터 9까지 가능한 수를 시도
        for (int num = 1; num <= 9; num++) {
            if (isValid(row, col, num)) {
                board[row][col] = num;
                if (solution(row, col + 1)) return true;
                board[row][col] = 0; // 되돌리기 (백트래킹)
            }
        }

        return false; // 모든 수가 실패한 경우
    }

    // 현재 위치에 num을 넣을 수 있는지 검사
    static boolean isValid(int row, int col, int num) {
        // 행과 열에 중복 확인
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num)
                return false;
        }

        // 3x3 박스 중복 확인
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (board[startRow + i][startCol + j] == num)
                    return false;

        return true;
    }
}

---

시간 복잡도

최악의 경우 빈칸이 모두 비어 있을 때는 가능한 숫자(1~9)를 모두 시도하므로 O(9^k)의 시간 복잡도를 가진다. (k: 빈칸의 개수)

완전 탐색처럼 보이지만 isValid() 함수로 가지치기를 하기 때문에 실제 탐색 수는 훨씬 적다.