[Leetcode]36. Valid Sudoku

문제 요약

• 알고리즘 분류: 구현
• 난이도: Medium
• 문제내용:
  • 문자형으로 스토쿠 배열을 준다. '.'은 비어 있는 공간이다.
  • 스도쿠를 보고 유효한 스도쿠인지 반환하여라.
• 사이트 주소: https://leetcode.com/problems/valid-sudoku/description/

문제풀이 

 이번 문제는 스도쿠 빈칸을 채우는 문제가 아니라 스도쿠판을 주고 이 판이 유효한지만 체크 하면된다. 그럼 구현 할것은 크게 2개라고 보면된다.

1. 가로, 세로 중복된 숫자 여부
2. 3 × 3 Box 안에 중복된 숫자 여부

 숫자 일때 아래 2개를 확인 하면 된다.

1. 가로, 세로 중복된 숫자 여부

  자기 위치 빼고 가로 세로 중복된 숫자 있는지 확인하면 된다. 

Python

def isCross(x, y, num):
    for i in range(9):
        if (i != y and board[x][i] == num) or (i != x and board[i][y] == num):
            return False
    return True

Java

public boolean isCross(int x, int y, int num){

    for(int i = 0; i < 9; i++){
        if((i != x && sudokuBoard[i][y] == num)|| (i != y && sudokuBoard[x][i] == num)){
            return false;
        }
    }

    return true;
}

2.  3 × 3 안에 중복된 숫자 여부

 x - (x % 3), y - (y % 3)는 박스의 시작점이다. 박스안에 중복된 숫자 있는지 확인하면 된다.

Python

def isBox(x, y, num):
    # 박스 가로, 세로 시작점
    boxX = x - (x % 3)
    boxY = y - (y % 3)

    for i in range(3):
        for j in range(3):
            if ((boxX + i != x) and (boxY + j != y)) and board[boxX + i][boxY + j] == num:
                return False

    return True

Java

public boolean isBox(int x, int y, int num){

    int boxX = x - (x % 3);
    int boxY = y - (y % 3);

    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if((boxX + i != x && (boxY + j != y) )  && sudokuBoard[i+boxX][j+boxY] == num){
                return false;
            }
        }
    }

    return true;
}

 

 

 스도쿠 판중에 거짓 하나라 나오면 거짓으로 반환하고 다 탐색하고 이상없으면 참으로 반환하기만 된다.

이번 문제는 스도쿠 판을 채울수 있는가였으면 백트레킹으로 풀면되지만 이 문제는 단순 스도쿠 판만 주고 유효한지만 판단하면 되기 때문에 어렵지 않을것이라고 생각한다. 자세한것은 아래 코드를 참조하기만 하면된다.

Code

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 가로, 세로 중복 숫자 찾는 함수
        def isCross(x, y, num):
            for i in range(9):
                if (i != y and board[x][i] == num) or (i != x and board[i][y] == num):
                    return False
            return True
        
        # 박스안에 중복 숫 찾는 함수
        def isBox(x, y, num):
            # 박스 가로, 세로 시작점
            boxX = x - (x % 3)
            boxY = y - (y % 3)

            for i in range(3):
                for j in range(3):
                    if ((boxX + i != x) and (boxY + j != y)) and board[boxX + i][boxY + j] == num:
                        return False

            return True

        # 스토쿠 유효하는 판단하는 함수
        def isSudoku(x, y, num):
            return isCross(x, y, num) and isBox(x, y, num)

        for i in range(9):
            for j in range(9):
                # 유효하지 않는 스토구는 바로 반환한다.
                if board[i][j] != '.' and (not isSudoku(i, j, board[i][j])):
                    return False

        return True

Java

class Solution {

    int[][] sudokuBoard;

    public boolean isValidSudoku(char[][] board) {

        sudokuBoard = new int[9][9];

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                sudokuBoard[i][j] = board[i][j] == '.'? 0 : board[i][j] - '0';
            }
        }

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(sudokuBoard[i][j] != 0 && !isSudoku(i, j, sudokuBoard[i][j])){
                    return false;
                }
            }
        }
        
        return true;
    }


    /*
     * 가로 세로 숫자가 있는지 판별하는 메소드
     */
    public boolean isCross(int x, int y, int num){

        for(int i = 0; i < 9; i++){
            if((i != x && sudokuBoard[i][y] == num)|| (i != y && sudokuBoard[x][i] == num)){
                return false;
            }
        }

        return true;
    }

    /*
     * 가로 세로 숫자가 있는지 판별하는 메소드
     */
    public boolean isBox(int x, int y, int num){

        int boxX = x - (x % 3);
        int boxY = y - (y % 3);

        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if((boxX + i != x && (boxY + j != y) )  && sudokuBoard[i+boxX][j+boxY] == num){
                    return false;
                }
            }
        }

        return true;
    }

    /*
     * 스도쿠 판별 가능한지 확인하는 메소드
     */
    public boolean isSudoku(int x, int y, int num){
        return isCross(x, y, num) && isBox(x, y, num);
    }
}