백준 - 스도쿠

문제 링크 ▶︎ 스도쿠

문제 파악

이 문제는 스도쿠의 빈칸이 정확하게 몇개인지 알려주지않아서 시간복잡도를 알 수는 없지만, 완전탐색으로 풀기 위해서는 빈칸의 갯수가 n이라고 가정했을 때, 9의 n제곱만큼 돌기 때문에 완전탐색으로는 어렵다.

그래서 백트래킹 + 가지치기를 해야하는데, 낮은 수부터 채워넣으면서 최초의 완성본이 나오면 바로 끝낼 수 있게 만든다.

접근 방법

1. 우선 특정 좌표에서 가로, 세로, 3x3 구역에 특정 수를 넣어도 되는지 검사하는 메서드를 각각 만든다. true, false로 리턴해 검사를 진행한다.

2. dfs로 해당 좌표에 숫자를 넣는데, 이미 빈칸의 좌표를 List로 받았기 때문에 해당 리스트를 순회하면서 1~9까지의 숫자를 넣는데 아까 만들어 둔 3개의 검사 메서드를 돌려서 모두 true가 나오면 그 숫자를 넣고 다음 인덱스로 넘겨준다.

3. 만약 빈칸을 모두 채워진 순간이라면 바로 flag를 true로 바꿔서 정답을 찾았음을 설정하고 리턴해준다. 그래야 이미 수행중인 find 함수가 바로 리턴돼서 시간일 줄어든다.

코드 구현

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

public class Main {
    public static boolean flag;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] sudoku = new int[9][9];
        List<int[]> empty = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            String line = br.readLine();
            for (int j = 0; j < 9; j++) {
                int v = Integer.parseInt(line.charAt(j) + "");
                sudoku[i][j] = v;
                if (sudoku[i][j] == 0) {
                    empty.add(new int[]{i, j});
                }
            }
        }
        flag = false;
        find(0,sudoku,empty);

    }
    public static void find(int dep, int[][] sudoku, List<int[]> empty) {
        if (flag) {
            return;
        }
        if (dep == empty.size()) {
            flag = true;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(sudoku[i][j]);
                }
                System.out.println();
            }
            return;
        }
        int y = empty.get(dep)[0], x = empty.get(dep)[1];
        for (int i = 1; i <= 9; i++) {
            if (vertical(i, x, sudoku) && horizontal(i, y, sudoku) && group(i, y, x, sudoku)) {
                sudoku[y][x] = i;
                find(dep + 1, sudoku, empty);
                sudoku[y][x] = 0;
            }
        }
    }
    public static boolean group(int i, int y, int x, int[][] sudoku) {
        int y_step = y / 3, x_step = x / 3;
        for (int j = y_step * 3; j < y_step * 3 + 3; j++) {
            for (int k = x_step * 3; k < x_step * 3 + 3; k++) {
                if (sudoku[j][k] == i) {
                    return false;
                }
            }
        }
        return true;
    }
    public static boolean horizontal(int i, int y, int[][] sudoku) {
        for (int j = 0; j < 9; j++) {
            if (sudoku[y][j] == i) {
                return false;
            }
        }
        return true;
    }
    public static boolean vertical(int i, int x, int[][] sudoku) {
        for (int j = 0; j < 9; j++) {
            if (sudoku[j][x] == i) {
                return false;
            }
        }
        return true;
    }
}

개선 사항

List를 쓰지말고 문제에 맞는 클래스를 생성해서 푸는 연습을 해야겠다.