[백준] 2580번 - 스도쿠 (Gold 4)

문제 링크

백준 2580번 - 스도쿠 (Gold 4)

문제 설명

주어진 스도쿠 문제를 풀면 된다. 문제는 반드시 풀 수 있으며, 답이 하나가 아니라면 하나만 출력해야 한다.

정답 코드 및 설명

빈 칸에 1~9를 각각 대입해보는 방식의 백트래킹이다.
주의할 점은 답이 될 수 없는 경우 대입해본 칸을 다시 0으로 돌려줘야 한다.
그대로 두게 되면 원래 문제가 변형되어 버린다.

시간을 줄이기 위해, 스도쿠 전체를 체크하지 않고 대입한 칸에 대해서만 체크를 진행하였다.
이것이 가능한 이유는 반드시 풀 수 있는 문제라는 전제가 있기 때문이다.

import java.io.*;
import java.util.*;

public class Main {

    static int sudoku[][]; // 스도쿠 문제 저장
    static ArrayList<Integer> blank = new ArrayList<>(); // 빈 칸의 인덱스 저장
    static StringBuilder sb = new StringBuilder();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        sudoku = new int[9][9];
        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = Integer.parseInt(st.nextToken());
                if (sudoku[i][j] == 0)
                    blank.add(i * 9 + j);
            }
        }
        solve(0);
    }

    // 백트래킹
    static void solve(int depth) throws IOException {
        // 이미 답이 나온 경우 출력 후 프로그램 종료
        if (depth == blank.size()) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(sudoku[i][j]);
                    sb.append(" ");
                }
                sb.append("\n");
            }
            bw.write(sb.toString());
            bw.close();
            System.exit(0);
        }
        for (int i = 1; i <= 9; i++) {
            if (isAble(blank.get(depth) / 9, blank.get(depth) % 9, i)) {
                sudoku[blank.get(depth) / 9][blank.get(depth) % 9] = i;
                solve(depth + 1);
            }
        }
        sudoku[blank.get(depth) / 9][blank.get(depth) % 9] = 0;
    }

    // 특정 칸과 숫자에 대해서만 체크(나머지는 이미 만족하고 있을 것이므로)
    static boolean isAble(int i, int j, int num) {
        for (int k = 0; k < 9; k++) {
            if (sudoku[i][k] == num)
                return false;
            if (sudoku[k][j] == num)
                return false;
            if (sudoku[3 * (i / 3) + k / 3][3 * (j / 3) + k % 3] == num)
                return false;
        }
        return true;
    }
}