[백준] 스도쿠 (2580)

문제 설명

백준 2580번 문제 링크

입력 및 출력

» 입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

» 출력

• 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다. 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

제한 사항

baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다. C++14: 80ms Java: 292ms PyPy3: 1172ms

예제 입출력(테스트케이스)

입력	출력
0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 5 3 2 1 0 4 6 8 9 7 8 0 4 9 1 3 5 0 6 5 9 6 8 2 0 4 1 3 9 1 7 6 5 2 0 8 0 6 0 3 7 0 1 9 5 2 2 5 8 3 9 4 7 6 0	1 3 5 4 6 9 2 7 8 7 8 2 1 3 5 6 4 9 4 6 9 2 7 8 1 3 5 3 2 1 5 4 6 8 9 7 8 7 4 9 1 3 5 2 6 5 9 6 8 2 7 4 1 3 9 1 7 6 5 2 3 8 4 6 4 3 7 8 1 9 5 2 2 5 8 3 9 4 7 6 1

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ2580_SWIFT
//
//  Created by choiyoujun on 2022/02/22.
//

import Foundation

var sudoku = Array(repeating: [Int](repeating: 0, count: 9), count: 9)
var checkCol = [[Bool]](repeating: [Bool](repeating: false, count: 10), count: 9)
var checkRow = [[Bool]](repeating: [Bool](repeating: false, count: 10), count: 9)
var subSudoku = Array(repeating: Array(repeating: [Bool](repeating: false, count: 10), count: 3), count: 3)
var q = [(x: Int, y: Int)]()

for i in 0..<9 {
    let arr = readLine()!.split(separator: " ").map { Int($0)! }
    sudoku[i] = arr
    
    for j in 0..<9 {
        checkRow[i][arr[j]] = true
    }
}

for i in 0..<9 {
    for j in 0..<9 {
        checkCol[i][sudoku[j][i]] = true
        subSudoku[i / 3][j / 3][sudoku[i][j]] = true
        
        if sudoku[i][j] == 0 {
            q.append((x: i, y: j))
        }
    }
}

func dfs() {
    if q.isEmpty {
        print(printSudoku())
        exit(0)
    }
    
    let next = q.removeFirst()
    for k in 0...9 {
        if !checkRow[next.x][k] && !checkCol[next.y][k] && !subSudoku[next.x / 3][next.y / 3][k] {
            checkRow[next.x][k] = true
            checkCol[next.y][k] = true
            subSudoku[next.x / 3][next.y / 3][k] = true
            sudoku[next.x][next.y] = k
            dfs()
            checkRow[next.x][k] = false
            checkCol[next.y][k] = false
            subSudoku[next.x / 3][next.y / 3][k] = false
            sudoku[next.x][next.y] = 0
        }
    }
    q.insert(next, at: 0)
}

func printSudoku() -> String {
    var str = ""
    for row in sudoku {
        for col in row {
            str.append("\(col) ")
        }
        str.append("\n")
    }
    return str
}

dfs()