문제번호	제목	난이도
2580번	스도쿠	골드 4

2580번 스도쿠

해결코드:

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


public class Main {

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[][] arr = new int[9][9];
        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());
            }
        }
        backtracking(arr,0,0);
        br.close();
        bw.close();
    }

    private static void backtracking(int[][] arr, int row, int col){
        if(col == 9){
            backtracking(arr,row+1, 0);
            return;
        }
        if(row == 9){
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(arr[i][j] + " ");
                }
                sb.append("\n");
            }
            System.out.println(sb.toString());
            System.exit(0);
        }


        if(arr[row][col] == 0){
            for (int i = 1; i <= 9; i++) {
                if(check(arr, row, col, i)){
                    arr[row][col] = i;
                    backtracking(arr, row, col+1);
                }
            }
            arr[row][col] = 0;
            return;
        }
        backtracking(arr, row, col+1);
    }

    private static boolean check(int[][] arr, int row, int col, int value){
        for (int i = 0; i < 9; i++) {
            if(arr[row][i] == value){
                return false;
            }
        }

        for (int i = 0; i < 9; i++) {
            if(arr[i][col] == value){
                return false;
            }
        }

        for (int i = (row / 3) * 3; i < (row / 3) * 3 + 3; i++) {
            for (int j = (col / 3) * 3; j < (col / 3) * 3 + 3; j++) {
                if(arr[i][j] == value){
                    return false;
                }
            }
        }
        return true;
    }

}

고민의 시간과 해결방법:

1. 개인적으로 백트래킹 구현에서 많이 어려웠던 문제였다.
2. 기능 구현은 간단하다. 조금 난해한게 있다면 33 배열에서 찾는 것 정도? 하지만 이것도 그래프를 생각해보면 쉽게 (row/3)3 ~ (row/3)*3 + 3범위 내에서 진행된다는 것을 알 수 있다. 물론 col도 마찬가지이다.
3. base condition을 어떻게 잡아야 할까 고민을 많이했다. 아무래도 배열이니까 depth는 아니고 row와 col로 잡아야할 것 같다고 생각하였다.
4. 먼저 col이 9이면 간단하게 다음 row을 탐색하면 된다
5. col이 9이면 배열을 모두 탐색했으므로 출력해주면 된다
6. 만약 해당 배열이 0이면 이제 만족하는 수를 찾아주어야 한다. 1~9까지 만족하는 수를 찾는데, 이때 앞서서 만든 같은열,같은행, 같은3*3범위 안에서 탐색을 진행해주고 만족하면 해당 수를 해당 배열에 넣은뒤 다시 백트래킹을 진행한다. 이때 탐색 방향이 같은 열 탐색 후 다음 행 방식이니까 col+1로 백트래킹을 진행한다
7. 만약 만족하는 수가 없으면 0으로 채워주고 return으로 종료한다
8. 해당 순회 종료 후, 다음 백트래킹을 진행해준다
9. 이 방식으로 진행했을 때, 만족하는 모든 경우를 찾을 수 있는데 문제에서는 한가지만 출력하라고 했다. 하지만 현재 구현 방식은 맞으나... 하나만 출력하기에는 너무 까다롭다. 그래서 선택한 방법이 System.exit(0)으로 강제로 종료시키는 방법이다
10. 다른 방법이 있을까 찾아봤으나 대부분 해당 방법을 택하였다. 이후 다시 문제를 풀게 된다면 더 깊이 생각해보고 탐색해볼 계획이다.

문제링크:

2580번 - 스도쿠