백준 2239번: 스도쿠 (JAVA)

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

2239번: 스도쿠

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

---

 

풀이

 

1. 스도쿠 판의 현재 상태 기록

• 다들 알겠지만, 스도쿠는 같은 행, 열, 3x3 칸에 같은 숫자가 있으면 안된다. 따라서 각 행, 열, 3x3 칸에 특정 숫자가 있는지를 2차원 boolean array로 기록해주자.
• rows[i][j]: i번째 row에 j가 있는가?
• cols[i][j]: i번째 col에 j가 있는가?
• smallBoards[i][j]: (왼쪽 위부터 아래쪽 오른쪽까지 책 읽는 방향으로) i번째 3x3 사각형에 j가 있는가?

 

2. 스도쿠 판 작성

• 백트래킹으로 기록한다.
• 편의를 위해 idx := 9*row + col이라는 변수를 0부터 81 이전까지 이동시키면서 체크한다.
• 만약 idx >= 81이라면: 끝에 도달하였다. 1부터 9까지 일일히 넣어보면서 체크하는 백트래킹 알고리즘은 사전식으로 검사하므로, 가장 먼저 구한 답이 정답이다. 그러므로 출력하고 프로그램을 끝낸다.
  • 만약 사전순의 반대로 출력하고 싶다면 백트래킹시 9부터 1까지 넣어보면 된다.
• idx를 row, col으로 변환시킨다.
• 만약 현 위치에 이미 숫자가 적혀있다면 다음칸으로 넘어간다.
• 적혀있지 않으면 1부터 9까지, 적을 수 있는 숫자는 적고 넘어간다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] rows = new boolean[9][10]; 
    static boolean[][] cols = new boolean[9][10];
    static boolean[][] smallBoards = new boolean[9][10]; // 3x3 칸들
    static int[][] board = new int[9][9];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 9; i++) {
            String str = br.readLine();
            for (int j = 0; j < 9; j++) {
                board[i][j] = str.charAt(j) - '0';
                rows[i][board[i][j]] = true;
                cols[j][board[i][j]] = true;
                smallBoards[3*(i/3) + (j/3)][board[i][j]] = true;
            }
        }
        sudoku(0);
    }


    static void sudoku(int idx) {
        if (idx >= 81) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(board[i][j]+"");
                }
                sb.append("\n");
            }
            System.out.println(sb.toString());
            System.exit(0); // 하나 찾으면 바로 끝
        }

        int r = idx / 9, c = idx % 9;

        if (board[r][c] != 0) sudoku(idx+1);

        else {
            for (int i = 1; i < 10; i++) {
                if (rows[r][i] || cols[c][i] || smallBoards[3*(r/3)+c/3][i]) continue;
                rows[r][i] = true;
                cols[c][i] = true;
                smallBoards[3*(r/3)+c/3][i] = true;
                board[r][c] = i;
                sudoku(idx+1);
                rows[r][i] = false;
                cols[c][i] = false;
                smallBoards[3*(r/3)+c/3][i] = false;
                board[r][c] = 0;
            }
        }
    }
}