[LeetCode] 36. Valid Sudoku - 구현(Implementation) JAVA

https://leetcode.com/problems/valid-sudoku/description/

코드설명

구현(Implementation) 을 활용합니다.

 

문제에서 유의할점은, 스도쿠를 만드는것이 아니라 스도쿠가 가능한지 여부를 판단합니다.

코드

정답 코드1입니다. 모든 i와 j를 돌면서 체크합니다.

좀더 개선시킨다면, 같은 3x3 박스에 속한다면 해당 부분에 대해서 3x3박스 유효성 체크를 안하도록 개선시킬 수 있습니다. (이떄 3x3박스 Index를 계산할떄 주의합니다. 해당 사항 디버깅에 오랜시간이 걸렸습니다.)

class Solution {
    char[][] Board;
    public boolean isValidSudoku(char[][] board) {
        Board = board;
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(isSolvable(i, j) == false){
                    return false;
                }         
            }
        }
        return true;
    }

    boolean isSolvable(int r, int c){
        int discovered = (1 << 9);
        int sR = r / 3;
        int sC = c / 3;
        for(int i = sR * 3; i < sR * 3 + 3; i++){
            for(int j= sC * 3; j < sC * 3 + 3; j++){
                if(Board[i][j] != '.'){
                    int num = Board[i][j] - '1';
                    if( (discovered & (1 << num)) > 0){
                        return false;
                    }else {
                        discovered += (1 << num);
                    }
                }
            }
        }        
        discovered = (1 << 9);
        for(int i=0; i<9; i++){
            if(Board[r][i] != '.'){
                int num = Board[r][i] - '1';
                if( (discovered & (1<< num)) > 0){
                    return false;
                }else {
                    discovered += (1 << num);
                }
            }
        }

        discovered = (1 << 9);
        for(int i=0; i<9; i++){
            if(Board[i][c] != '.'){
                int num = Board[i][c] - '1';
                if( (discovered & (1<< num)) > 0){
                    return false;
                }else {
                    discovered += (1 << num);
                }
            }
        }
        return true;
    }

}

 

정답코드2입니다.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character>[] row = new HashSet[9];
        HashSet<Character>[] col = new HashSet[9];
        HashSet<Character>[] box = new HashSet[9];

        for(int i=0; i<9; i++){
            row[i] = new HashSet<Character>();
            col[i] = new HashSet<Character>();
            box[i] = new HashSet<Character>();
        }

        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j] != '.'){
                    int boxIndex = (i / 3) * 3 + (j / 3);
                    if(row[i].contains(board[i][j]) == true || col[j].contains(board[i][j]) == true || box[boxIndex].contains(board[i][j]) == true ){
                        return false;
                    }
                    row[i].add(board[i][j]);
                    col[j].add(board[i][j]);
                    box[boxIndex].add(board[i][j]);                    
                }
            }
        }
        return true;
    }


}

 

오답코드1입니다. 처음에 문제를 잘못 읽고 풀었습니다.

저의 경우, 스도쿠를 완성시킬 수 있느냐 없느냐를 생각하여 직접 스도쿠를 완성시킨 코드입니다.

그와는 별개로, 아래의 코드에서 checkBowRowCol함수에는 오류도 존재합니다. 3x3 box부분에 오류가 있는 점을 알 수 있습니다.

class Solution {
    char[][] Board;
    public boolean isValidSudoku(char[][] board) {
        Board = board;
        System.out.print(DFS(0, 0));

        return false;
    }

    boolean DFS(int r, int c){
        if(c >= 9) { r = r + 1; c = 0; }
        if(r >= 9) {return true;}
        boolean ret = false;
        if(Board[r][c] == '.'){
            int discovered = (1 << 10);
            int newDiscovered = checkBoxRowCol(r, c, discovered);
            for(int i=1; i<10; i++){
                //IF THERE IS NOT NUM USED
                if( (newDiscovered & (1 << i)) == 0){
                    // System.out.print("i:"+i);
                    Board[r][c] = Character.forDigit(i, 10);
                    ret |= DFS(r, c + 1);
                }
            }
            Board[r][c] = '.';
        } else {
            ret |= DFS(r, c + 1);
        }

        return ret;
    }

    int checkBoxRowCol(int r, int c, int discovered){
        int sR = r / 3;
        int sC = c / 3;
        // System.out.print("SR:"+sR+"SC:"+sC);
        for(int i = sR; i < sR + 3; i++){
            for(int j= sC; j < sC + 3; j++){
                if(Board[i][j] != '.'){
                    int num = Board[i][j] - '0';

                    if( (discovered & (1 << num)) > 0){
                        discovered = 1 << 10 - 1;
                    }else {
                        discovered |= (1 << num);
                    }
                }
            }
        }

        //If there is a num in LINE_ROW, LINE_COL, then it cannot work.

        for(int i=0; i<9; i++){
            if(Board[r][i] != '.'){
                int num = Board[r][i] - '0';
                if( (discovered & (1<< num)) > 0){
                    discovered = 1 << 10 - 1;
                }else {
                    discovered |= (1 << num);
                }
            }

            if(Board[i][c] != '.'){
                int num = Board[i][c] - '0';
                if( (discovered & (1<< num)) > 0){
                    discovered = 1 << 10 - 1;
                }else {
                    discovered |= (1 << num);
                }
            }
        }

        return discovered;
    }
}