[알고리즘] 백준 2580 - 스도쿠

문제본문

스도쿠 규칙

• 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
• 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

백트래킹이란 가능하지 않는 집합을 배제하는 완전 탐색(브루트포스)을 의미합니다. 모든 경우의 수를 구하지만 정답이 아닐 확률이 높다면 시도하지 않는 것이죠. 때문에 완전탐색보다 빠른 시간안에 정답을 구현할 수 있습니다.
관련 알고리즘의 흐름과 설명은 참고 링크에 더 자세히 나와 있습니다.

스도쿠 입력

9 x 9 스도쿠판에 0 ~ 9 숫자 값이 들어 있습니다. 빈칸은 여러개 존재할 수 있으며 빈칸은 0으로 표시합니다.

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

스도쿠 출력

빈칸을 모두 스도쿠 규칙에 알맞게 숫자를 대입한 후 완성된 스도쿠 판을 출력합니다. 단, 답이 여러개 일경우 한 경우만 출력합니다.

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

해설

쉬운 접근을 위해 스도쿠 초기 값을 저장할 int[][] 변수를 선언합니다. 이후 값이 비어있는 빈칸의 위치를 따로 저장합니다. 그 이유는 매번 반복할 때마다 모든 스도쿠 판을 돌면서 빈칸을 찾는 것은 비효율 적이기 때문입니다. 이차원 배열이기 때문에 위치 값을 뜻하는 클래스를 선언해줍니다.

탐색은 빈칸에 어떠한 값을 차례대로 넣는 것입니다. 총 9개의 빈칸이 있다면 처음 빈칸에 1을 넣어보고 그 다음 빈칸에 1을 또 넣어보고 안되면 2를 넣어보는 등 위 순서로 진행되며 이 과정에서 백트래킹의 유망성 검증이 들어갑니다. 앞서 말한 스도쿠의 규칙에 따라 빈칸에 넣는 숫자의 값이 유효한지 판단합니다. 만약 유효하다면 계속 진행이 되고, 모든 숫자의 경우의 수가 규칙과 어긋난다면 그 이전 빈칸으로 돌아가 숫자를 초기화해주어야 합니다.
탐색의 깊이가 빈칸의 수와 동일해지는 경우는 스도쿠과 완성된 경우이며 출력을 진행하고 시스템을 완전히 종료시킵니다.

 

답

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException{
        Scanner scanner = new Scanner(System.in);

        ArrayList<BlankPosition> blanks = new ArrayList<>();
        int[][] board = new int[9][9];

        for (int height = 0; height < 9; height++) {
            for (int width = 0; width < 9; width++) {
                int num = scanner.nextInt();

                if (num == 0) {
                    blanks.add( new BlankPosition(width, height));
                }

                board[height][width] = num;
            }
        }

        dfs(board, blanks, 0);

    }

    //빈칸 탐색하는 함수
    public static void dfs(int[][] board, ArrayList<BlankPosition> blankPosition, int index) throws IOException {
        if (index == blankPosition.size()) {
            print(board);
            System.exit(0);
        }

        for (int num = 1; num < 10; num++) {
            BlankPosition blank = blankPosition.get(index);
            if (widthCheck(board, blank, num) && heightCheck(board, blank, num) && squareCheck(board, blank, num)) {
                board[blank.height][blank.width] = num;
                dfs(board, blankPosition, index + 1);
                board[blank.height][blank.width] = 0;  // 안될경우 이전 탐색의 값을 초기화
            }
        }
    }

    //전체 출력
    public static void print(int[][] board) throws IOException {
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String temp;
        for (int i = 0; i < 9; i++) {
            temp = "";
            for (int j = 0; j < 9; j++) {
                temp += " " + board[i][j];
            }
            temp = temp.substring(1) + "\n";
            writer.write(temp);
        }

        writer.close();
    }

    //스도쿠 1번째 규칙 중 가로 검사
    public static boolean widthCheck(int[][] board, BlankPosition blank, int value) {
        for (int width = 0; width < 9; width++) {
            if (blank.width != width && board[blank.height][width] == value) {
                return false;
            }
        }
        return true;
    }

    //스도쿠 1번째 규칙 중 세로 검사
    public static boolean heightCheck(int[][] board, BlankPosition blank, int value) {
        for (int height = 0; height < 9; height++) {
            if (blank.height != height && board[height][blank.width] == value) {
                return false;
            }
        }
        return true;
    }

    // 스도쿠 2번째 규칙 중 3x3 정사각형 검사
    public static boolean squareCheck(int[][] board, BlankPosition blank, int value) {
        int startWidth = 3 * (blank.width / 3);
        int startHeight = 3 * (blank.height / 3);

        for (int width = startWidth; width < startWidth + 3; width++) {
            for (int height = startHeight; height < startHeight + 3; height++) {
               if (board[height][width] == value && height != blank.height && width != blank.width) {
                   return false;
               }
            }
        }

        return true;
    }

    //빈칸의 위치를 저장하는 클래스
    static class BlankPosition {
        int width;
        int height;

        BlankPosition(int width, int height) {
            this.width = width;
            this.height = height;
        }
    }
}

 

참고

• 되추적(Backtracking) 알고리즘