[Java] leetcode 37. Sudoku Solver

문제

LeetCode - The World's Leading Online Programming Learning Platform

Sudoku Solver - LeetCode

알아야 할 개념

• brute force 구현
• 재귀 함수

풀이

2d 배열에 스토쿠를 빈칸없이 완성하는 문제.

로직은 다음과 같다.

1. 각 행, 열, 박스 (3*3) 행렬 의 숫자를 담을 set을 3개 생성한다.
2. 주어진 스토쿠를 순회하면서, '.' 문자이면 x, y 좌표를 저장한다.
3. 숫자 문자이면, set 에 담는다.
4. 재귀 함수를 만든다.
   1. Level이 '.' 문자 좌표 개수만큼 도달하면 종료한다. 
   2. 각 위치마다 1~9 의 숫자가 해당 행, 열 , 박스 에서 유효한 숫자인지(중복이 없는지) 체크하고 재귀 호출을 한다.

 

참고

box 의 index 설정은 다음과 같다. 

(i/3)*3 + (j/3)

DFS 탐색 시 정답이 나왔으면 flag 를 만들어서 더이상 탐색 종료 되게 만들어야 한다. 

안 그러면 정답이 아닌 지점을 모두 탐색 완료하여 배열에 정답이 아닌 값들이 들어가기 때문이다.

 

코드

class Solution {
    HashSet<Integer>[] row ;
    HashSet<Integer>[] col ;
    HashSet<Integer>[] box ;
    int N = 9;
    boolean flag = false;
    int[][] P;
    int cnt;
    public void solveSudoku(char[][] board) {
        row = new HashSet[N];
        col = new HashSet[N];
        box = new HashSet[N];
        P = new int[2][82];//비어있는 위치 저장
        cnt = 0;
        
        for(int i = 0 ;i < N; i++){
            row[i] = new HashSet<Integer>();
            col[i] = new HashSet<Integer>();
            box[i] = new HashSet<Integer>();
        }
        for(int i = 0 ; i< N ;i++){
            for(int j =0 ;j < N ;j++){
                if(board[i][j] == '.'){
                    P[0][cnt] = i;
                    P[1][cnt++] = j;
                }else{
                    int x = (board[i][j] - '0');
                    row[i].add(x);
                    col[j].add(x);
                    box[(i/3)*3 + (j/3)].add(x);
                }
            }
        }
        dfs(0, board);
    }
    public void dfs(int L, char[][]board){
        if(L == cnt){
            flag = true;
            return;
        }
        if(flag)return ;

        int x = P[0][L];
        int y = P[1][L];

        for(int k = 1 ; k < 10 ;k++){
            if(flag)return;
            int n = k;
            if(row[x].contains(n) || col[y].contains(n) || box[(x/3)*3+(y/3)].contains(n))continue;
            row[x].add(n);
            col[y].add(n);
            box[(x/3)*3+(y/3)].add(n);
            board[x][y] = (char)(k + '0');
            dfs(L+1, board);
            row[x].remove(n);
            col[y].remove(n);
            box[(x/3)*3+(y/3)].remove(n);
        }
    }
}