03/28 코딩테스트 문제풀이 - 37. Sudoku Solver (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 37. Sudoku Solver(Hard)
• 문제 내용 : [링크]
  ![]
  
  

내가 작성한 코드

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:

        def is_valid(r, c, num, board):
            for i in range(9):
                # 가로(행) 숫자 판별
                if board[r][i] == num:
                    return False

                # 세로(열) 숫자 판별
                if board[i][c] == num:
                    return False
                
                # 3*3 숫자 판별
                if board[3*(r//3)+i//3][3*(c//3)+i%3] == num:
                    return False
            return True
    
        def backtrack(index, board):
            if index == 81:
                return True

            r, c = index//9, index%9

            if board[r][c] == '.':
                for num in map(str, range(1, 10)):
                	if is_valid(r, c, k, board):
                    	board[r][c] = k
                    	if backtrack(index+1, board):
                        	return True
                    	board[r][c] = '.'
                return False
            else:
                return backtrack(index+1, board)

        backtrack(0, board)

• 스도쿠 규칙에 따라 2차원 배열을 완성하는 문제이다.

• is_valid(r, c, num, board) 함수를 통해,

  1. 가로행에 해당 숫자 존재여부 판별
     if board[r][i] == num:

  2. 세로열에 해당 숫자 존재여부 판별
     if board[i][c] == num:

  3. 해당 좌표 기준, 3x3 칸에 해당 숫자존재여부 판별
     if board[3*(r//3)+i//3][3*(c//3)+i%3] == num:

• backtrack(index, board) 함수를 통해 (0,0) 부터 (8,8)까지 완전탐색해준다.

• 이 때, index의 몫과 나머지를 이용하여 r, c를 구해주어 2차원배열 모든 좌표를 완전탐색 해준다.

• 해당좌표가 빈칸 '.'일 때,

  1. 1~9 숫자를 넣어주면서 is_valid 함수를 통해 스도쿠 규칙 준수 여부를 확인한다.

  2. 규칙을 준수한다면, 해당 값을 업데이트 해주고, 재귀를 통해 다음 좌표로 넘어간다.

  3. 끝까지 스도쿠 모든 칸을 완성하면 (index==81일 때) True를 반환한다.

  4. 아닌 경우, 업데이트 했던 좌표를 다시 빈칸으로 만들어준다.

• 해당좌표가 빈칸이 아닌 경우, index+1 해준 후, 재귀를 통해 다음 좌표로 넘어간간다.

⭐⭐⭐⭐⭐

• index의 몫과 나머지를 통해 for문 처럼 모든 2차원 배열의 좌표를 완전탐색 할 수 있다.(r, c = index//9, index%)

• 해당 좌표가 빈칸이 아닌 경우에도 완전탐색을 진행할 수 있도록 else: return backtrack(index+1, board) 해준다.

• for num in map(str, range(1, 10))를 통해, 숫자를 str으로 바꾸는 구현법 확인