[BOJ] 2239번 스도쿠 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static int[][] map = new int[9][9];

    public static void main(String[] args) throws IOException {
        init();
        solve(0, 0);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 9; i++) {
            String input = br.readLine();
            for (int j = 0; j < 9; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
    }

    private static void solve(int row, int col) {
        // 마지막 열에 도착하면 다음 행으로 이동
        if (col == 9) {
            solve(row + 1, 0);
            return;
        }
        // 마지막 행에 도착하면 출력 후 종료
        if (row == 9) {
            print();
            System.exit(0);
        }

        // 현재 위치가 빈칸인 경우 유효성 검사
        if (map[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (check(row, col, i)) {
                    map[row][col] = i;  // 가능한 숫자를 넣기
                    solve(row, col + 1);    // 다음 열 확인
                }
            }
            map[row][col] = 0;  // 값 복귀를 해줘야함
            return;
        }
        solve(row, col + 1);    // 다음 열 확인
    }

    private static void print() {
        StringBuilder result = new StringBuilder();
        for (int[] ints : map) {
            for (int i : ints) {
                result.append(i);
            }
            result.append("\n");
        }
        System.out.println(result);
    }

    private static boolean check(int row, int col, int num) {
        // 열검사
        for (int i = 0; i < 9; i++) {
            if (map[row][i] == num) {
                return false;
            }
        }

        // 행검사
        for (int i = 0; i < 9; i++) {
            if (map[i][col] == num) {
                return false;
            }
        }

        // 현재 위치가 포함된 3X3 영역 검사
        int r = (row / 3) * 3;
        int c = (col / 3) * 3;
        for (int i = r; i < r + 3; i++) {
            for (int j = c; j < c + 3; j++) {
                if (map[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}

📄 해설

• 스도쿠를 푸는 조건을 코드로 구현하는 문제
• 스도쿠 퍼즐을 풀기위한 조건
  1. 같은 열에 1~9 까지의 숫자가 중복 없이 나와야함
  2. 같은 행에 1~9 까지의 숫자가 중복 없이 나와야함
  3. 3X3 보드에 1~9 까지의 숫자가 중복 없이 나와야함
• 위 조건에 따라 조건 검사 메소드를 작성하여 조건을 검사함
• 행과 열에 대한 검사는 단순하나, 3X3 영역 검사 부분은 현재 선택된 위치가 속한 3X3 영역을 검사해야하므로, 약간의 계산이 필요함(이 부분은 직접 계산하지 않으면 이해가 안됨)
• 문제를 푸는 것은 가장 왼쪽 위의 칸에서부터 시작하며, 첫번째 행의 모든 열을 완수하고 다음 행으로 넘어감
• 답이 여러개 있을 수 있으므로, 가장 먼저 완성된 스도쿠 퍼즐을 출력으로 함