[BOJ 2580] 스도쿠 (Java)

#문제

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

2580번: 스도쿠

#풀이

백트래킹, DFS를 이용하여 풀었다. 

1. 스도쿠 정보를 2차 배열에 담는다. 

2. 0값의 좌표를 ArrayList로 들고 있는다. 

3. 특정 좌표에 특정 Value가 할당 될 수 있는지 체크하는 함수를 생성한다. (isPossible()로 구현)

- 좌표가 속한 세로, 가로, 3*3 정사각형 좌표에서 Value가 이미 존재하는지 체크한다. 

4. ArrayList의 0번째 index부터 재귀함수를 돌면서 1~9까지의 값이 유효한지 체크를 한다.

올바른 값이 있다면 해당 좌표에 값을 할당하고, 다음 index의 재귀함수를 호출한다. 

만약 for문이 모두 끝났다면 1~9까지의 모든 수가 불가능한 것이므로 좌표의 값을 원복 시킨다. 

이렇게 함수가 끝나면 해당 함수를 호출했던 로직의 다음 절차가 진행된다.  

5. 재귀함수의 매개변수인 k가 zeroCnt와 동일하다면 모든 0좌표의 값이 채워진 것이므로 스도쿠 배열을 출력한다. 

올바른 스도쿠판은 여러 개가 나올 수 있기 때문에 이때 프로그램을 종료시켜야 시간 초과 문제가 발생하지 않는다.

 

#소스코드

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

public class BOJ2580 {

    public static int[][] arr;
    public static ArrayList<int[]> zeros;
    public static int zeroCnt;

    public static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new int[9][9];
        zeros = new ArrayList<>();

        // 스도쿠 정보를 2차 배열에 담는다.
        // 이 때, 0 값을 갖는 좌표를 ArrayList에 저장한다.
        for(int i = 0; i < 9; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 9; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 0){
                    zeros.add(new int[]{i, j});
                }
            }
        }

        // 0값의 개수를 int 변수에 저장한다.
        zeroCnt = zeros.size();
    }

    public static void recur(int k){
        // k 값이 0의 개수에 도달했다면 모든 0 좌표의 값이 채워진 것이므로 프로그램을 종료시킨다.
        // 올바른 스도쿠판이 여러개가 될 수 있으므로, 가장 처음에 채워진 스도쿠 판으로 print 하고 프로그램을 종료시켜야 한다.
        // 종료시키지 않으면 시간초과 발생
        if(k == zeroCnt){
            printSudoku();
            System.exit(0);
        }

        // 0 좌표의 값을 구한다.
        int[] xy = zeros.get(k);
        int x = xy[0]; int y = xy[1];

        // 1~9 값을 차례대로 넣어보면서 넣을 수 있는지 체크하고 넣는게 가능하다면 해당 값을 배열에 할당하고 k+1로 recur함수를 호출한다.
        // 그러면 다음 index의 0값을 채우는 로직이 반복된다.
        // recur 함수를 호출했지만 다음 index에서 1~9값이 모두 불가능할 경우, 다시 이전 recur함수로 되돌아 와서 다음 index를 체크하게 된다.
        // 만약 for문이 끝났다면 모든 경우의 수가 맞지 않는 것이므로 해당 배열의 값을 다시 0으로 원복시킨다.
        // 이렇게 함수가 끝나면 이 함수를 호출한 recur 함수의 다음 절차가 실행됨.
        // 재귀 함수는... 머리가 핑핑 돈다.
        for(int i = 1; i <= 9; i++){
            if(isPossible(x, y, i)){
                arr[x][y] = i;
                recur(k+1);
            }
            if(i==9) arr[x][y] = 0;
        }
    }

    public static boolean isPossible(int x, int y, int val){
        // 가로 체크
        for(int i = 0; i < 9; i ++){
            if(i == x) continue;
            if(val == arr[i][y]) return false;
        }
        // 세로 체크
        for(int i = 0; i < 9; i++){
            if(i == y) continue;
            if(val == arr[x][i]) return false;
        }
        // 해당 좌표가 속한 3*3 정사각형 좌표의 값을 체크
        for(int i = (x/3)*3; i < (x/3)*3+3; i++){
            for(int j = (y/3)*3; j < (y/3)*3+3; j++){
                if(i == x && j == y) continue;
                if(val == arr[i][j]) return false;
            }
        }
        return true;
    }

    public static void printSudoku(){
        for(int i = 0; i < 9; i++){
            for(int j =0 ; j < 9; j++){
                System.out.print(arr[i][j]);
                if(j < 8) System.out.print(" ");
            }
            if(i < 8) System.out.println();
        }
    }

    public static void main(String[] args) throws Exception {
        input();
        // zero 좌표의 정보를 가지고 있는 ArrayList의 원소를 재귀함수를 거치면서 값을 채워나갈 것이다.
        recur(0);
    }
}