[JAVA]백준 2239번 스도쿠

📌문제 링크

---

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

📌문제 설명

---

백트래킹 정석문제입니다. 모든 빈칸에 가능 숫자들을 전부 넣어보면서 다 채워졌을때 보드를 출력하면 됩니다. 사전 순으로 출력해야하는 조건은 백트래킹을 구현하면 자동으로 해결되기 때문에 생각 안해도 됩니다. 시간제한도 넉넉해서 최적화를 하지 않아도 통과 가능합니다.

📌코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

// 좌표를 저장하는 Pair 클래스
class Pair {
    int x;
    int y;

    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[][] sudoku = new int[9][9];
    static List<Pair> v = new ArrayList<>();
    static boolean[][] rowCheck = new boolean[9][10];  // 행 중복 체크
    static boolean[][] colCheck = new boolean[9][10];  // 열 중복 체크
    static boolean[][] squareCheck = new boolean[9][10];  // 3x3 영역 중복 체크

    public static void main(String[] args) throws Exception {
        input(); // 입력 처리
        solve(); // 스도쿠 풀기
    }

    // 스도쿠 풀이를 시작하는 메서드
    public static void solve() throws Exception {
        backTracking(0); // 백트래킹 시작
    }

    // 백트래킹을 이용한 스도쿠 풀이 메서드
    public static void backTracking(int index) throws Exception {
        if (index == v.size()) { // 모든 빈 칸을 채웠을 때
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(sudoku[i][j]);
                }
                sb.append("\n");
            }
            bw.write(sb.toString());
            bw.flush();
            bw.close();
            System.exit(0);
        }

        Pair pair = v.get(index); // 현재 빈 칸의 좌표
        int x = pair.x;
        int y = pair.y;
        int squareIndex = (x / 3) * 3 + (y / 3); // 3x3 영역 인덱스 계산

        for (int i = 1; i <= 9; i++) {
            if (!rowCheck[x][i] && !colCheck[y][i] && !squareCheck[squareIndex][i]) {
                sudoku[x][y] = i;
                rowCheck[x][i] = colCheck[y][i] = squareCheck[squareIndex][i] = true;

                backTracking(index + 1);

                // 되돌리기
                sudoku[x][y] = 0;
                rowCheck[x][i] = colCheck[y][i] = squareCheck[squareIndex][i] = false;
            }
        }
    }

    // 입력 처리 메서드
    public static void input() throws Exception {
        for (int i = 0; i < 9; i++) {
            String line = br.readLine();
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = line.charAt(j) - '0';
                if (sudoku[i][j] == 0) {
                    v.add(new Pair(i, j)); // 빈 칸 좌표 추가
                } else {
                    // 초기 상태 설정
                    rowCheck[i][sudoku[i][j]] = true;
                    colCheck[j][sudoku[i][j]] = true;
                    int squareIndex = (i / 3) * 3 + (j / 3);
                    squareCheck[squareIndex][sudoku[i][j]] = true;
                }
            }
        }
    }
}