[BOJ] 2239. 스도쿠

문제 원본 : https://www.acmicpc.net/problem/2239

2239번: 스도쿠

import java.io.*;

public class Main {
    public static char[][] sudoku;
    public static int[][] pos = new int[81][2];
    public static int cnt = 0;
    public static boolean isSolved = false;

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

        sudoku = new char[9][9];
        for (int i = 0; i < 9; ++i) {
            sudoku[i] = br.readLine().toCharArray();
        }

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (sudoku[i][j] == '0') {
                    pos[cnt][0] = i;
                    pos[cnt++][1] = j;
                }
            }
        }

        solve(0);

        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                builder.append(sudoku[i][j]);
            }
            builder.append("\n");
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }

    public static void solve(int idx) {
        if (idx == cnt) {
            isSolved = true;
            return;
        }

        for (char c = '1'; c <= '9'; ++c) {
            if (isValid(pos[idx][0], pos[idx][1], c)) {
                sudoku[pos[idx][0]][pos[idx][1]] = c;

                solve(idx + 1);

                if (isSolved) {
                    return;
                }

                sudoku[pos[idx][0]][pos[idx][1]] = '0';
            }
        }
    }

    public static boolean isValid(int r, int c, char ch) {
        for (int i = 0; i < 9; ++i) {
            if (sudoku[r][i] == ch) {
                return false;
            }
        }

        for (int i = 0; i < 9; ++i) {
            if (sudoku[i][c] == ch) {
                return false;
            }
        }

        int rs = r / 3 * 3;
        int cs = c / 3 * 3;
        for (int i = rs; i < rs + 3; ++i) {
            for (int j = cs; j < cs + 3; ++j) {
                if (sudoku[i][j] == ch) {
                    return false;
                }
            }
        }

        return true;
    }
}

• 백 트래킹 문제
• 처음에 0인 위치의 좌표 배열을 만들고
• 작은 숫자부터 넣어 보면서 안 되면 되돌리는 방식으로 해결 가능하다.