LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 스도쿠 문제가 담긴 이중 배열 board
2. output: 스도쿠를 완성하여 리턴
3. 각 칸은 스도쿠 룰에 맞춰 숫자가 채워짐

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

Idea

빈칸에 대하여 가능한 숫자를 체크(행,열,박스에 없는 숫자)하여 DFS → Sol1

Solution

1. DFS

   • 빈칸 찾기
   • 해당 빈칸에 가능한 숫자 찾기
   • 숫자 삽입 후 재귀 탐색
   • 빈칸이 하나도 없을 경우 정답으로 리턴

   class Solution {
       fun solveSudoku(board: Array<CharArray>): List<CharArray>? {
           return dfs(board.toList())
       }
   
       fun dfs(board: List<CharArray>): List<CharArray>? {
           for (r in board.indices) {
               for (c in board[0].indices) {
                   if (board[r][c] == '.') { // 빈칸
                       for (num in 1..9) {
                           if (check(board, r, c, num.toString())) {
                               board[r][c] = num.toString()[0]
                               val result = dfs(board)
                               if (result != null) return result
                               else board[r][c] = '.'
                           }
                       }
                       return null
                   }
               }
           }
           return board // 빈칸이 하나도 없을 경우 정답
       }
   
       fun check(tmp: List<CharArray>, r: Int, c: Int, num: String): Boolean {
           if (tmp[r].contains(num[0])) return false // 행 검사
           for (row in tmp.indices) { // 열 검사
               if (tmp[row][c].toString() == num) return false
           }
           // 3X3 박스 검사
           for (row in (r/3*3)..(r/3*3 + 2)) {
               for (col in (c/3*3)..(c/3*3 + 2)) {
                   if (tmp[row][col].toString() == num) return false
               }
           }
           return true
       }
   }
   

   시간 복잡도: 이중 배열 순회(빈칸 찾기) X 이중 배열 순회(빈칸 찾기) X …

   

Point

1. 발전 방향
   • 숫자가 많이 채워진 박스부터 탐색
   • 숫자가 많이 채워진 행부터 탐색
   • 숫자가 많이 채워진 열부터 탐색