[Algorithm] 백준 - 2580번 스도쿠 (Swift)

문제 소개

https://www.acmicpc.net/problem/2580
스도쿠를 채우는 문제이다.
 

문제 풀이

스도쿠에서 빈칸을 저장한뒤 그 빈칸에 하나하나 입력해주고, 결과가 나오면 exit(0) 를 통해서 값을 내보낸다.

import Foundation

var sudoku = [[Int]]()
var blank = [[Int]]()

// 입력 받기
for _ in 0..<9 {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    sudoku.append(input)
}

// 빈칸 조사
for i in 0..<9 {
    for j in 0..<9 {
        if sudoku[i][j] == 0 {
            blank.append([i, j])
        }
    }
}

// 가로, 세로 줄 판별
func line(_ n: Int, _ i: Int, _ j: Int) -> Bool {
    for k in 0..<9 {
        if sudoku[i][k] == n || sudoku[k][j] == n {
            return false
        }
    }
    
    return true
}

// 사각형 판별
func square(_ n: Int, _ i: Int, _ j: Int) -> Bool {
    for k in 0..<3 {
        for l in 0..<3 {
            if sudoku[i/3*3+k][j/3*3+l] == n {
                return false
            }
        }
    }
    
    return true
}

// 스도쿠 채우기
func dfs(_ depth: Int) {
    if depth == blank.count {
        for line in sudoku {
            print(line.map { String($0) }.joined(separator: " "))
        }
        exit(0)
    }
    
    for i in 1...9 {
        let y = blank[depth][0]
        let x = blank[depth][1]
        
        if line(i, y, x) && square(i, y, x) {
            sudoku[y][x] = i
            dfs(depth+1)
            sudoku[y][x] = 0
        }
    }
}

dfs(0)

 
결과는 392ms 로 준수(?) 하게 나왔다. Knuth's Algorithm 이라는 알고리즘을 쓰면 4ms 도 가능하다는데... 다이아 2 수준의 알고리즘이라고 한다. 좀더 공부를 한뒤 다시 풀어봐야겠다.