📙[Algo] 24.03.03 알고리즘

알고리즘 문제) BOJ 2239. 스도쿠

• 링크 : https://www.acmicpc.net/problem/2239

문제 요약

• 99 크기의 보드가 있을 때, 같은 행과 열 그리고, 9개의 33 크기 보드에 1~9까지 숫자를 중복 없이 채워야 함
• 하다 만 스도쿠 퍼즐이 주어졌을 때 마저 끝내기!

시간 제한

• 2초

입력

• 9개의 줄에 9개의 숫자로 보드가 입력
• 숫자가 채워지지 않은 칸에는 0이 주어짐

출력

• 9개의 줄에 9개의 숫자로 답
• 만약 여러 개가 있다면 사전식으로 가장 앞서는 것을 출력(즉, 81자리 수가 제일 작은 경우 출력)

접근법

• 일단 같은 행, 같은 열, 같은 3*3 사각형 내에서 숫자 방문체크하는 배열과 메소드를 만들어야 한다.
• 1부터 가능한 숫자들을 채워가면서 최초로 완성되는 스도쿠 퍼즐을 출력한다.

코드

import java.io.*;

public class Main {
    static boolean[][] rowCheck = new boolean[9][10];
    static boolean[][] colCheck = new boolean[9][10];
    static boolean[][] squareCheck = new boolean[9][10];
    static int[][] map = new int[9][9];
    static boolean isFinish = false;
    static StringBuilder sb;

    static int square(int row, int col) {
        return (row / 3) * 3 + (col / 3);
    }

    static void recur(int row, int col) {

        if(isFinish) return;

        if (col == 9) {
            col = 0;
            row++;
        }

        if (row == 9) {
            sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(map[i][j]);
                }
                sb.append("\\n");
            }
            isFinish = true;
            return;
        }

        if (map[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (rowCheck[row][i] || colCheck[col][i]
                        || squareCheck[square(row, col)][i]) continue;

                rowCheck[row][i] = true;
                colCheck[col][i] = true;
                squareCheck[square(row, col)][i] = true;
                map[row][col] = i;

                recur(row, col + 1);

                rowCheck[row][i] = false;
                colCheck[col][i] = false;
                squareCheck[square(row, col)][i] = false;
                map[row][col] = 0;
            }
            return;
        } else {
            recur(row, col + 1);
        }
    }

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

        String input;
        for (int i = 0; i < 9; i++) {
            input = br.readLine();

            for (int j = 0; j < 9; j++) {
                map[i][j] = input.charAt(j) - '0';

                if (map[i][j] != 0) {
                    rowCheck[i][map[i][j]] = true;
                    colCheck[j][map[i][j]] = true;
                    squareCheck[square(i,j)][map[i][j]] = true;
                }
            }
        }

        recur(0, 0);

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}