[백준] 2580번 : 스도쿠 (java)

2580번: 스도쿠 (acmicpc.net)

2580번: 스도쿠

어떻게 생각하고 문제를 풀었는가?

하나의 빈칸에 숫자를 올바르게 채워넣기 위해서는 다음의 조건들을 만족해야 합니다.

1. 같은 가로 줄에 있는 숫자들과 중복되는가?

2. 같은 세로 줄에 있는 숫자들과 중복되는가?

3. 3x3으로 정의되는 정사각형 안에 있는 숫자들과 중복되는가?

이러한 방식으로 가능한 숫자를 빈칸에 대입한 후 다른 빈칸에서도 조건을 만족하는 숫자가 존재하지 않는다면 이전 빈칸의 숫자를 바꾸어 반복하는 Back-Tracking 방식으로 문제를 해결할 수 있겠다고 생각하였습니다.

코드

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

//2580
class Main {
    static int[][] arr;
    static boolean[][] rowNums, colNums, boxNums;
    static List<Pos> list;
    static class Pos{
        int x;
        int y;
        Pos(int y, int x){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws IOException {
        arr = new int[9][9];
        rowNums = new boolean[9][9+1];
        colNums = new boolean[9][9+1];
        boxNums = new boolean[9][9+1];
        list = new ArrayList<>();
        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++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==0){
                    list.add(new Pos(i,j));
                }else{
                    rowNums[i][arr[i][j]] = true;
                    colNums[j][arr[i][j]] = true;
                    boxNums[(i/3)*3+j/3][arr[i][j]] = true;
                }
            }
        }
        check(0);
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                sb.append(arr[i][j]);
                sb.append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
        br.close();
    }
    static boolean check(int index){
        if(index == list.size()) return true;
        Pos cur = list.get(index);
        int box = (cur.y/3)*3+cur.x/3;
        for(int i=1; i<=9; i++){
            if(!rowNums[cur.y][i]&&!colNums[cur.x][i]&&!boxNums[box][i]){
                rowNums[cur.y][i] = true;
                colNums[cur.x][i] = true;
                boxNums[box][i] = true;
                arr[cur.y][cur.x] = i;
                if(check(index+1)) return true;
                rowNums[cur.y][i] = false;
                colNums[cur.x][i] = false;
                boxNums[box][i] = false;
                arr[cur.y][cur.x] = 0;
            }
        }
        return false;
    }
}

Back-Tracking 방식은 재귀함수를 통해 구현할 수 있습니다.

스도쿠의 빈칸에 들어갈 수 있는 숫자는 1~9뿐입니다.

가로 줄, 세로 줄, 3x3 정사각형에 사용된 숫자들을 boolean 배열로 정의하여 저장한다면 하나의 반복문, 하나의 조건문으로 대입가능한 숫자를 찾아낼 수 있습니다.

다음 빈칸에서 대입가능한 숫자가 없는 경우 이전 빈칸에서 숫자를 대입한 과정을 복구하고, 다른 대입가능한 숫자를 찾음으로써 모든 경우의 수를 확인할 수 있습니다.