[JAVA]백준 2580번 스도쿠

📌문제 링크

---

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

📌문제 설명

---

전형적인 백트래킹 문제입니다. 각 빈칸마다 1에서 9까지의 수를 넣는 경우를 백트래킹으로 완전탐색하면 됩니다.

📌코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 좌표를 저장하는 Pair 클래스
class Pair {
    int x, 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 int[][] sudoku = new int[9][9]; // 스도쿠 판
    static ArrayList<Pair> empty = new ArrayList<>(); // 빈 칸 좌표 리스트
    static int cnt = 0; // 빈 칸 개수

    public static void main(String[] args) throws Exception {
        input(); // 입력 받기
        backTracking(0); // 백트래킹 시작
    }

    // 입력을 받는 메서드
    public static void input() throws Exception {
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 9; j++) {
                sudoku[i][j] = Integer.parseInt(st.nextToken());
                if(sudoku[i][j] == 0) {
                    empty.add(new Pair(i, j)); // 빈 칸 좌표 저장
                }
            }
        }
        cnt = empty.size(); // 빈 칸 개수 저장
        br.close();
    }

    // 행을 검사하는 메서드
    public static boolean checkRow(int x, int num) {
        for(int i = 0; i < 9; i++) {
            if(sudoku[x][i] == num) {
                return false;
            }
        }
        return true;
    }

    // 열을 검사하는 메서드
    public static boolean checkCol(int y, int num) {
        for(int i = 0; i < 9; i++) {
            if(sudoku[i][y] == num) {
                return false;
            }
        }
        return true;
    }

    // 3x3 박스를 검사하는 메서드
    public static boolean checkBox(int x, int y, int num) {
        int startX = x / 3 * 3;
        int startY = y / 3 * 3;
        for(int i = startX; i < startX + 3; i++) {
            for(int j = startY; j < startY + 3; j++) {
                if(sudoku[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }

    // 백트래킹 메서드
    public static void backTracking(int idx) {
        if(idx == cnt) {
            // 스도쿠 완성 시 출력 후 종료
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    System.out.print(sudoku[i][j] + " ");
                }
                System.out.println();
            }
            System.exit(0); // 프로그램 종료
        }

        Pair p = empty.get(idx);
        int x = p.x;
        int y = p.y;
        for(int i = 1; i <= 9; i++) {
            if(checkRow(x, i) && checkCol(y, i) && checkBox(x, y, i)) {
                sudoku[x][y] = i;
                backTracking(idx + 1);
                sudoku[x][y] = 0; // 백트래킹
            }
        }
    }
}