백준 2580 스도쿠

https://www.acmicpc.net/problem/2580

9 x 9 스도쿠 판이 주어지고, 판을 채우는 경우 하나를 출력하는 문제이다.

판이 9 x 9칸으로 비교적 작은 크기로 고정이고, 숫자도 1~9로 작은 범위이므로 dfs를 통해 직접 케이스를 구해보기로 하였다.

먼저 input을 받고 0이 입력된 빈칸들의 r(row), c(column)값을 모았다.
(빈 칸들에 가능한 숫자들을 넣어 볼 것이기 때문)

위 예시에서는 (0, 0), (1, 4), (1, 7) ... 등 빈칸을 모은다.

다음 dfs함수를 통해 각 빈 칸에 대해 넣을 수 있는 후보들을 구하고, 각 후보들에 대해 해당 칸에 입력 후 다음 빈 칸으로 넘어가도록 구현한다.

위 예시에서는 (0, 0)칸에 대해 넣을 수 있는 후보는 1 하나이다.

(0, 0)칸에 1을 넣은 후, dfs(idx + 1)를 호출하여 (1, 4)칸으로 이동한다.

이동 후 (1, 4)에서도 넣을 수 있는 숫자 후보를 구하고 넣고 다음으로 이동하고를 반복한다.

그렇게 idx가 빈 칸의 개수만큼 진행되면, 필드를 출력하고 종료한다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val field = Array(9){ readLine().split(' ').map{it.toInt()}.toTypedArray()}
    val empties = getEmptyPoses(field)

    var find = false
    fun dfs(emptyIdx: Int){
        if(find) return
        if(emptyIdx == empties.size) {
            for(i in 0 until 9){
                for(j in 0 until 9){
                    print("${field[i][j]} ")
                }
                println()
            }
            find = true
            return
        }

        val empty = empties[emptyIdx]
        val candidates = getCandidateNumbers(empty, field)

        for(cd in candidates){
            field[empty.r][empty.c] = cd
            dfs(emptyIdx + 1)
            field[empty.r][empty.c] = 0
        }
    }

    dfs(0)
}

fun getCandidateNumbers(pos: Pos, field: Array<Array<Int>>): List<Int>{
    val candidates = (0..9).toList()
    val ck = BooleanArray(10){true}

    for(i in 0 until 9){
        val value = field[i][pos.c]
        ck[value] = false
    }

    for(i in 0 until 9){
        val value = field[pos.r][i]
        ck[value] = false
    }

    val boxR = (pos.r / 3) * 3
    val boxC = (pos.c / 3) * 3

    for(i in boxR..boxR + 2){
        for(j in boxC..boxC + 2){
            val value = field[i][j]
            ck[value] = false
        }
    }

    return candidates.filterIndexed { index, _ -> ck[index] }
}

fun getEmptyPoses(field: Array<Array<Int>>): List<Pos>{
    val list = mutableListOf<Pos>()
    for(i in 0 until 9){
        for(j in 0 until 9){
            if(field[i][j] == 0)
                list.add(Pos(i, j))
        }
    }
    return list
}

data class Pos(
    val r: Int,
    val c: Int
)

위에서 설명한 과정을 그대로 작성하였다.

getEmptyPoses 함수는 0이 입력된 빈 칸들을 모아 반환하는 함수이다.

find 변수는 한 케이스를 찾으면 더 이상 진행하지 않도록 하기 위한 플래그이다.

getCandidateNumbers함수는 해당 빈 칸에 넣을 수 있는 숫자 후보들을 골라내는 함수이다.

0~9까지 숫자에 true로 표시를 해 두고, 가로 세로 사각형에 존재하는 숫자들에 대해 false로 표시한다.

그리고 true인 숫자들을 후보로 넘겨준다.