백준 스도쿠

문제

내가 생각했을때 문제에서 원하는부분

9개의 줄에 9개의 숫자로 보드가 입력된다.
아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

9개의 줄에 9개의 숫자로 답을 출력한다.
답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다.
즉, 81자리의 수가 제일 작은 경우를 출력한다.

내가 이 문제를 보고 생각해본 부분

board 배열에 스도쿠 보드 상태를 저장한다.
solved는 해답을 찾았음을 나타내는 플래그이다.
main에서 9줄의 입력을 받아 board에 저장한다.
solve 함수가 (row, col)에서 시작해서 백트래킹으로 빈 칸을 순차적으로 채워 나간다.
만약 현재 칸이 숫자로 채워져 있으면 다음 칸으로 넘어간다.
빈 칸일 경우 1부터 9까지 숫자를 시도하면서 canPlace 함수로 조건 검사를 한다.
조건에 맞으면 그 숫자를 넣고 다음 칸으로 탐색을 계속한다.
더는 넣을 수 없으면 0으로 초기화(backtracking)하고 다시 이전 단계로 돌아간다.
canPlace 함수는 스도쿠 규칙에 맞는지 행, 열, 그리고 3x3 박스 내에 중복 숫자가 없는지 검사한다.
next 함수는 현재 위치에 따라 다음 칸으로 이동하는 역할을 합니다. 마지막 열은 다음 행 첫 열로 넘어간다.
모든 칸을 무사히 채우면 solved 플래그를 true로 바꾸고 재귀를 종료한다.
마지막에 완성된 board를 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 백준 2239번 문제
public class Main1335 {
    static int[][] board = new int[9][9];
    static boolean solved = false;

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

        // 보드 입력
        for (int i = 0; i < 9; i++) {
            String line = br.readLine();
            for (int j = 0; j < 9; j++) {
                board[i][j] = line.charAt(j) - '0';
            }
        }

        solve(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();
        }

        br.close();
    }

    // 백트래킹 함수: (row, col) 위치부터 시작
    static void solve(int row, int col) {
        if (row == 9) { // 모든 행을 다 채우면
            solved = true;
            return;
        }
        if (board[row][col] != 0) { // 이미 숫자가 채워진 칸
            next(row, col);
        } else {
            for (int num = 1; num <= 9; num++) {
                if (canPlace(row, col, num)) {
                    board[row][col] = num;
                    next(row, col);
                    if (solved)
                        return; // 답 찾으면 종료
                    board[row][col] = 0; // 백트래킹
                }
            }
        }
    }

    // 다음 칸으로 이동하는 함수
    static void next(int row, int col) {
        if (col == 8) {
            solve(row + 1, 0);
        } else {
            solve(row, col + 1);
        }
    }

    // 현재 위치에 num을 놓을 수 있는지 검사
    static boolean canPlace(int row, int col, int num) {
        // 행 검사
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num)
                return false;
        }
        // 열 검사
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num)
                return false;
        }
        // 3x3 박스 검사
        int boxStartRow = (row / 3) * 3;
        int boxStartCol = (col / 3) * 3;
        for (int i = boxStartRow; i < boxStartRow + 3; i++) {
            for (int j = boxStartCol; j < boxStartCol + 3; j++) {
                if (board[i][j] == num)
                    return false;
            }
        }
        return true;
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.