[Leetcode/파이썬] 36. Valid Sudoku

Valid Sudoku

---

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

 

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

 

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)
        cols = defaultdict(set)
        boxes = defaultdict(set)

        for r in range(9) :
            for c in range(9) :
                if board[r][c] == '.' :
                    continue
                    
                if board[r][c] in rows[r] or board[r][c] in cols[c] or board[r][c] in boxes[(r//3, c//3)] :
                    return False

                rows[r].add(board[r][c])
                cols[c].add(board[r][c])
                boxes[(r//3, c//3)].add(board[r][c])

        return True

스도쿠가 성립하기 위한 정의를 다시 한 번 살펴보자. 

• 가로 행에 동일한 숫자가 없을 경우
• 세로 열에 동일한 숫자가 없을 경우
• 작은 박스 안에 동일한 숫자가 없을 경우

이렇게 세 가지 조건을 모두 성립하는 방진이 스도쿠이다. 그렇다면, 해당 스도쿠가 성립하는지 살펴보기 위해서는 하나하나씩 숫자를 뽑아가면서 기존에 있던 숫자인지 체크하면 된다. 

그리고 defaultdict() 자료구조에 대해서 일반적인 dict를 쓰면 안되는지에 대해서 공부해보니, defaultdict를 이용하면 add할 때 해당 키가 없을 경우, 자동 생성한다. 그러나 dict의 경우, 생성하는 코드를 따로 작성해주어야 하기 때문에 이와 같은 문제를 해결하기 위해서는 defaultdict 이 라이브러리를 활용하는 것이 좋겠다.