[백준 *Java] - 스도쿠(2580)

스도쿠

2580번: 스도쿠

문제

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

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

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

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

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

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

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

입력

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

출력

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

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

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

---

 

👇 접근방식 

문제를 볼 때, 백트래킹으로 생각을하면 되겠다고 생각을 했습니다.
일단 스도쿠를 풀어보셨거나? 무엇인 지 안다면 규칙을 알 수 있습니다.
row(가로), column(세로), 3By3 Martrix(행렬) 이 1부터 9까지 중복없이 수가 들어가야한다는 규칙입니다.
그래서, 문제를 풀 땐 백트래킹으로 Martix 에 빈 곳(0)을 기준으로 가로(1~9), 세로(1~9), 3x3Matrix(1~9) 에 있는 수 중에서 없는 수를 뽑아서 그 수를 가지고 백트래킹을 시도하는 방향으로 짠다고 생각을 했습니다.

예시 예제입력1 기준.
x,y(0,0) 위치에 빈 곳(0)이 있으니 그걸로 설명을 해보겠습니다.
1,2,3,4,5,6,7,8,9 중에서
남은 수 중에서 0행의 위치에 있는 숫자(7,3,8,5,9,6,2)를 지웁니다.
1,4
남은 수 중에서 0열의 위치에 있는 숫자(4)를 지웁니다.
1
남은 수 중에서 3by3 위치에 있는 숫자(x)를 지웁니다.
결과는 1 입니다.
이런 식으로 결과값이 여러 개인 경우는 백트래킹(가지치기)를 이용하여 값을 찾아가는 방식으로 로직을 설계하면 될 거 같습니다.

그리고 3By3 Matrix에 있는 1~9까지 값을 찾기 위해서는 나머지를 이용해서 3By3 Matrix 위치 내에 있는 숫자를 탐색할 수 있게끔 값을 변환해준 뒤 for문 루프를 돌게 끔 구현해주면 됩니다.

 

아래는 성공한 코드입니다

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

public class Boj_2580 {
    static final int MATRIX_SIZE = 9;
    static int[][] board = new int[MATRIX_SIZE][MATRIX_SIZE];

    static void printBoard() {
        StringBuilder sb = new StringBuilder();
        for (int row = 0; row < MATRIX_SIZE; row++) {
            for (int column = 0; column < MATRIX_SIZE; column++) {
                sb.append(board[row][column]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    // Row(행) 를 확인합니다.
    static boolean isNumberInRow(int number, int row) {
        for (int i = 0; i < MATRIX_SIZE; i++) {
            if (board[row][i] == number) {
                return true;
            }
        }
        return false;
    }
    // Col(열) 를 확인합니다.
    static boolean isNumberInColumn(int number, int column) {
        for (int i = 0; i < MATRIX_SIZE; i++) {
            if (board[i][column] == number) {
                return true;
            }
        }
        return false;
    }

    // 3x3 매트릭스 내에 수가 있는지 확인 메서드
    static boolean isNumberIn3By3Matrix(int number, int row, int column) {
        int start3By3MatrixRow = row - (row % 3);
        int start3By3MatrixColumn = column - (column % 3);
        // ex (5,3) 일 경우, (3,3) 으로 변환하는 과정
        for (int i = start3By3MatrixRow; i < start3By3MatrixRow + 3; i++) {
            for (int j = start3By3MatrixColumn; j < start3By3MatrixColumn + 3; j++) {
                if (board[i][j] == number) {
                    return true;
                }
            }
        }
        return false;
    }

    // 세 조건이 유효한 지 확인하는 메서드
    static boolean isValid(int number, int row, int column) {
        return !isNumberInRow(number, row) &&
                !isNumberInColumn(number, column) &&
                !isNumberIn3By3Matrix(number, row, column);
    }

    // 스도쿠 풀이를 위한 메서드
    static boolean dfs() {
        // 이중 for loop 를 돌면서,
        for (int row = 0; row < MATRIX_SIZE; row++) {
            for (int column = 0; column < MATRIX_SIZE; column++) {

                // 스도쿠 map 에 빈 곳(0)이라면? In
                if (board[row][column] == 0) {
                    for (int i = 1; i <= MATRIX_SIZE; i++) {
                        if (isValid(i, row, column)) { // 세 가지 조건이 true 라면?
                            board[row][column] = i; // 그 타입을 저장
                            if (dfs()) return true;
                            else board[row][column] = 0; // backtracking
                        }
                    }
                    // * 스도쿠를 해결할 수 없음. 따라서 return false.
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for (int i = 0; i < MATRIX_SIZE; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < MATRIX_SIZE; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs();
        printBoard();
    }
}