[BOJ] 2580번 : 스도쿠 (JAVA/자바)

문제

---

알고리즘 고민

빈 공간인 0에 1부터 9까지 차례대로 넣으면서 스도쿠의 기본 원리인 3x3 칸 + 가로 9칸 + 세로 9칸 검사를 진행하고 가능하면 넣은 후 dfs로 탐색을 진행하는 방법으로 작성하였다.

 

1. 입력 값인 스도쿠를 for문을 이용해서 값이 0 인곳(빈칸)을 탐색해서 blankIdx 라는 ArrayList 배열에 빈 공간의 point를 전부 담아 놓는다. (탐색하는 시간을 조금이라도 줄이려고 한 과정이지만 사실 차이는 없을 것 같아 어차피 탐색은 n개를 O(n)으로 탐색하기 때문에...

2. dfs 방식으로 탐색을 하면서 숫자를 넣었는데, 만약 모든 빈칸이 꽉 찼다면(blankIdx.size() == cnt(채운 숫자 개수)) 현재의 스도쿠 상태를 출력하고 프로그램을 종료한다.

3. 숫자를 넣을때1~9까지의 숫자를 차례대로 넣으면서 가능한지 여부를 판단하는 canBatch 메소드를 이용해 검사하고 가능하다면 다음 dfs로 진행하였다.

4. canBatch는 가로 세로에 같은 숫자가 있는지 검사를 진행하고 이후 해당 숫자가 위치한 3x3 칸의 숫자내부에서 체크를 진행하였다.

---

JAVA Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int[][] sudoku;
    static ArrayList<Point> blankIdx;

    public static class Point {
        int y, x;

        public Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void dfsSudoku(int cnt) {
        if (blankIdx.size() == cnt) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 9; i++) {
                sb.append(sudoku[i][0]);
                for (int j = 1; j < 9; j++) {
                    sb.append(' ').append(sudoku[i][j]);
                }
                sb.append('\n');
            }

            System.out.print(sb.toString().strip());
            System.exit(0);
        }

        Point p = blankIdx.get(cnt);

        for (int i = 1; i <= 9; i++) {
            if (canBatch(p, i)) {
                sudoku[p.y][p.x] = i;
                dfsSudoku(cnt + 1);
            }
        }
    }

    public static boolean canBatch(Point p, int value) {
        // 가로 세로 검사
        for (int i = 0; i < 9; i++) {
            if (value == sudoku[p.y][i]) {
                return false;
            }

            if (value == sudoku[i][p.x]) {
                return false;
            }
        }

        // 3 x 3 검사
        int xRange = (p.x / 3) * 3;
        int yRange = (p.y / 3) * 3;
        for (int i = yRange; i < yRange + 3; i++) {
            for (int j = xRange; j < xRange + 3; j++) {
                if (value == sudoku[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }

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

        sudoku = new int[9][9];
        blankIdx = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = Integer.parseInt(st.nextToken());
                if (sudoku[i][j] == 0) {
                    blankIdx.add(new Point(i, j));
                }
            }
        }

        dfsSudoku(0);
    }
}