[백준] 스도쿠 : 2580번 - 자바(JAVA)

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

문제 해석

스도쿠란 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타나야 합니다.

또한  3x3 정사각형 안에도 1~9까지의 숫자가 한번씩만 나타나야 합니다.

 

스도쿠의 빈칸의 경우에는 0으로 채워져 있으며 스도쿠 판을 채우는 방법이 여럿인 경우에는 그중 하나만을 출력합니다.

 

문제 풀이전 설계

스도쿠를 실제로 채우는 것처럼 진행해보고자 합니다.

재귀 함수를 통해서 해당 칸에 들어갈 수 있는 모든 수들을 대입해보며 정말 탐색합니다.

 

빈칸의 가로줄 세로줄 1~9 유효성 검사

빈칸을 포함하는 3x3 1~9 유효성 검사

 

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

public class Main_2580_스도쿠 {
    static final int SIZE = 9;
    static int[][] board = new int[SIZE][SIZE];
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    static class EmptySpace {

        int y;
        int x;

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

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

        StringTokenizer st = null;
        for (int y = 0; y < SIZE; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < SIZE; x++) {
                board[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        //입력 끝
        List<EmptySpace> emptySpaces = new ArrayList<>();
        for (int y = 0; y < SIZE; y++) {
            for (int x = 0; x < SIZE; x++) {
                if (board[y][x] != 0) {
                    continue;
                }
                //0을 가지고 있는 y,x 좌표의 위치를 탐색합니다.
                emptySpaces.add(new EmptySpace(y, x));
            }
        }
        //스도쿠 시작
        inputNumbers(0, emptySpaces);

    }

    private static void inputNumbers(int count, List<EmptySpace> emptySpaces) {
        if (count == emptySpaces.size()) {
            //모든 수가 정상적으로 잘 채워졌습니다.
            printBoard();
            System.exit(0);
        }


        EmptySpace cur = emptySpaces.get(count);

        //i번째 빈공간에 대하여 넣을 수 있는 숫자를 탐색
        boolean[] validNumbers = getValidNumbers(cur.y, cur.x);

        //1~9까지의 숫자를 넣어봄
        for (int j = 1; j <= 9; j++) {
            if (!validNumbers[j]) {
                continue;
            }

            //어떤 수를 넣을 수 있다면 다음 빈칸을 채워보도록 하자
            board[cur.y][cur.x] = j;
            inputNumbers(count + 1, emptySpaces);
            board[cur.y][cur.x] = 0;
        }


    }


    private static void printBoard() {
        StringBuilder sb = new StringBuilder();
        for (int y = 0; y < SIZE; y++) {
            for (int x = 0; x < SIZE; x++) {
                sb.append(board[y][x] + " ");
            }
            sb.append("\n");
        }

        System.out.print(sb.toString());
    }

    private static boolean[] getValidNumbers(int y, int x) {

        boolean[] validNumbers = new boolean[SIZE + 1];
        Arrays.fill(validNumbers, true);

        //세로줄 유효성 검사
        for (int i = 0; i < SIZE; i++) {
            validNumbers[board[i][x]] = false;
            validNumbers[board[y][i]] = false;
        }

        //0,1,2 = startY = 3 * 0
        //3,4,5 = startY = 3 * 1
        //6,7,8 = startY = 3 * 2
        int startY = 3 * (y / 3);
        int startX = 3 * (x / 3);
        // 주변 3x3 배열도 탐색해서 후보로 올 수 있는 수 탐색
        for (int i = startY; i < startY + 3; i++) {
            for (int j = startX; j < startX + 3; j++) {
                validNumbers[board[i][j]] = false;
            }
        }

        return validNumbers;
    }

    private static boolean isValid(int tempY, int tempX) {
        return tempY >= 0 && tempY < SIZE && tempX >= 0 && tempX < SIZE;
    }
}