백준 - 2239번(스도쿠)

문제 출처: https://www.acmicpc.net/problem/2239

문제

• 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

• 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

• 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

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

public class Main {

    private static List<int[]> target;
    private static StringBuilder sb;

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

        int[][] sudoku = new int[9][9];

        target = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            char[] temp = reader.readLine().toCharArray();

            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = temp[j] - '0';
                if (sudoku[i][j] == 0) target.add(new int[] { i, j });
            }
        }

       dfs(sudoku, 0);

        System.out.println(sb);
    }

    private static void dfs(int[][] sudoku, int idx) {
        if (sb != null) return;

        if (idx == target.size()) {
            sb = new StringBuilder();

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

            return;
        }

        int y = target.get(idx)[0];
        int x = target.get(idx)[1];

        boolean[] temp = new boolean[10];

        checkCross(sudoku, temp, y, x);
        checkInner(sudoku, temp, y / 3 * 3, x / 3 * 3);

        for (int k = 1; k < 10; k++) {
            if (!temp[k]) {
                sudoku[y][x] = k;
                dfs(sudoku, idx + 1);
                sudoku[y][x] = 0;
            }
        }
    }

    // 가로, 세로 체크
    private static void checkCross(int[][] sudoku, boolean[] temp, int r, int c) {
        for (int i = 0; i < 9; i++) {
            if (sudoku[r][i] != 0) temp[sudoku[r][i]] = true;

            if (sudoku[i][c] != 0) temp[sudoku[i][c]] = true;
        }
    }

    // 내부 3x3 사각형 체크
    private static void checkInner(int[][] sudoku, boolean[] temp, int r, int c) {
        for (int i = r; i < r + 3; i++) {
            for (int j = c; j < c + 3; j++) {
                if (sudoku[i][j] != 0) temp[sudoku[i][j]] = true;
            }
        }
    }

}

• 상당히 오랜 시간이 걸려 문제를 풀었다.
• 처음 해결한 방법은 메모리와 시간이 상상을 초월하는 수준이었다.
  
• 특별히 깨닫게 된 것은, dfs를 이때까지는 더이상 진행할 수 없으면 다른 곳으로 가는 용도로만 사용했었는데, 다시 그 자리를 다른 값으로 채우는 방식도 가능함을 알게 되었다.
• 여러가지 쓸데없는 규칙들을 고려하느라 시간이 많이 걸렸는데, 좀 더 로직을 체계적으로 세우는 연습이 필요한 것 같다.