<Algorithm> 187. 스도쿠(BJO)

1. 2580번 스도쿠(BJO)

   사용 알고리즘 :  DFS, 백트래킹

• 처음에 이걸 완전탐색으로 풀수 있을까 라는 의문이 들었다. 왜냐면 9가지 숫자에 대한 경우의 수이므로 한줄에만 9! 발생했다.

• 그래서 규칙을 활용 해야하는건가 해서 힌트를 봤는데 백트래킹 카테고리였고 가로,세로, 3*3에대한 부분을 체크가 필요했다.  

• 이걸 보고 저 세가지조건을 만족하는 경우의 수는 1억번 연산 이하로 가능 할 것이라는 느낌이 왔다(+n은 9*9로 고정)

• 보통 백트래킹할때 기존의 값을 다시 복구 시켜주는 방법을 사용하는데 그래서 0으로 놓고 진행했다.

• 문제는 스도쿠에 0은 존재 할 수 없다. 그리고 로직이 0을 카운팅하기 때문에 시간초과가 발생해버렸다.

• 해결방법은 탐색이 끝난 위치는 더이상 진행할 필요가 없게 하면된다. (1~9 경우가 끝나면 종료)

문제에 대한 접근&생각

1. 빈자리에 모든 경우의 수를 해본다. -> 모든 자리가 0일때 9!*9!*~ 어마무시한 연산량 발생  
2. 될 수 없는 숫자가 존재 -> 3가지 조건에 맞지 않을 경우 탐색 X -> 백트래킹!, DFS!

내 코드 

import java.util.Scanner;
 
public class Main {
    static int[][] map;
    static int count;
    public static void main(String[] args) {
        /***************************
         * DFS 백트래킹을 이용해서 모든
         * 경우를 탐색한다. 이때 스도쿠 조건인
         * 가로, 세로, 3*3 그룹에 대한 체크
         * 를 포함한다.
         ***************************/
        Scanner sc = new Scanner(System.in);
        map = new int[9][9];
        count = 0;
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                map[i][j] = sc.nextInt();
                if(map[i][j]==0) count++;
            }
        }
        
        solve(0);
    }
    private static void print() {
        //System.out.println();
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void solve(int deep) {
        //print();
        if(count == deep) {
            print();
            System.exit(0);
            return;
        }
        
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(map[i][j] == 0) {
                    for(int k = 1; k <= 9; k++) {
                        if(isBoundary(i, j, k)) {
                            map[i][j] = k;
                            solve(deep+1);
                            map[i][j] = 0;
                            // 0으로 하는 이유는
                            // 조건체크할때 포함해서 체크하기 때문
                        }
                    }
                    return; // 탐색 필요없음 스도쿠에 0은 존재하지 않기때문
                }
            }
        }
    }
    static int[] chg = {0,0,0,3,3,3,6,6,6};
    public static boolean isBoundary(int x, int y, int target) {
        for(int i = 0; i < 9; i++) {
            if(map[i][y] == target||map[x][i]==target) {
                return false;
            }
        }
        x = chg[x];
        y = chg[y];
        for(int i = x; i < x+3; i++) {
            for(int j = y; j<y+3; j++ ) {
                if(map[i][j]==target)
                    return false;
            }
        }
        return true;
    }
}