[BOJ] 2580. 스도쿠 - JAVA

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

2580번: 스도쿠

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

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

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

---

난이도 

solved.ac 티어 기준 gold 4 문제.

접근방법

문제를 읽자마자 전형적인 백트래킹 문제라고 생각했다.

모든 경우의 수를 조사하기 위해서는 9^(빈칸개수) 만큼의 시간복잡도가 필요하지만, 가능성이 없는 경우는 그 다음 과정으로 넘어가지 않음으로써 주어진 시간 내에 문제해결이 가능하다.

 

풀이 과정

1. 빈칸에 대한 좌표를 저장

2. 각 빈칸에 대해 중복순열 알고리즘을 사용해 모든 경우의 수를 탐색한다.

3. 조건식을 추가하여 유망하지 않은 경우 탐색을 하지 않는다.

 

풀이 코드

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

public class Boj_2580_스토쿠 {
    static int[][] board = new int[9][9];
    static ArrayList<int[]> emptyPoint = new ArrayList<>();

    static int[][] writeBoard = new int[9][9];
    static boolean isSolved = false;

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

        StringTokenizer st;

        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                int num = Integer.parseInt(st.nextToken());
                board[i][j] = num;
                if (num == 0) {
                    emptyPoint.add(new int[]{i, j});
                }
            }
        }
        for(int i = 0; i < 9; i++){
            writeBoard[i] = board[i].clone();
        }

        backTracking(0);
    }
    
    // 2. 각 빈칸에 대해 중복순열 알고리즘을 사용해 모든 경우의 수를 탐색한다.
    private static void backTracking(int depth) {
        if (depth == emptyPoint.size()) {
            printSdoku(writeBoard);
            isSolved = true;
            return;
        }

        for (int i = 1; i <= 9; i++) {
            if(isSolved){
                return;
            }
            
            // 3. 조건식을 추가하여 유망하지 않은 경우 탐색을 하지 않는다.
            if (isPromising(writeBoard, depth, i)) {
                int[] point = emptyPoint.get(depth);
                writeBoard[point[0]][point[1]] = i;
                backTracking(depth + 1);
                writeBoard[point[0]][point[1]] = 0;
            }
        }
    }
	
    // 조건식 - 가로, 세로, 박스에 대해 num을 놓을 수 있으면 true, 불가능하면 false 리턴
    private static boolean isPromising(int[][] board, int depth, int num) {
        int[] point = emptyPoint.get(depth);

        // 가로, 세로
        for (int i = 0; i < 9; i++) {
            if (board[point[0]][i] == num) {
                return false;
            }

            if (board[i][point[1]] == num) {
                return false;
            }
        }

        // 박스
        for (int i = point[0] / 3 * 3; i < point[0] / 3 * 3 + 3; i++) {
            for (int j = point[1] / 3 * 3; j < point[1] / 3 * 3 + 3; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
	
    // 스도쿠를 출력한다.
    private static void printSdoku(int[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}