2580번: 스도쿠 - kotlin (DFS)

2580번: 스도쿠

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

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

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

나의 풀이

 이 문제는 DFS를 이용해서 스도쿠의 빈칸을 채워나가면 되는 문제이다. (0, 0)부터 스도쿠 판에 마지막까지 진행하면서 마지막 칸까지 도착했을때 DFS를 멈추고 출력을 하면 되겠다. 기존의 우리가 스도쿠를 해결할 때 처럼 문제를 진행하면 생각보다 어렵게 된다. 수학적으로 접근하려고 생각하지 말고 무차별적으로 대입해나가면서 가지를 뻗쳐 나가면 된다.

 

exitProcess(0)

 라는 현재 프로세스를 강제로 종료할 수 있는 명령어를 배우는 기회가 되었다.

 

import kotlin.system.exitProcess

var board = Array(0) { IntArray(0) }
fun main() = with(System.`in`.bufferedReader()) {
    board = Array(9) { readLine().split(" ").map { it.toInt() }.toIntArray() }

    dfs(0, 0)
}

fun dfs(x: Int, y: Int) {
    if (y == 9) {
        dfs(x + 1, 0)
        return
    }

    if (x == 9) {
        board.forEach {
            it.forEach { print("$it ") }
            println()
        }
        exitProcess(0)
    }

    if (board[x][y] == 0) {
        for (i in 1 until 10) {
            if (check(x, y, i)) {
                board[x][y] = i
                dfs(x, y + 1)
            }
        }
        board[x][y] = 0
        return
    }
    dfs(x, y + 1)
}

fun check(x: Int, y: Int, value: Int): Boolean {
    board[x].forEach {
        if (it == value)
            return false
    }

    for (i in 0 until 9) {
        if (board[i][y] == value)
            return false
    }

    val tempX = when(x) {
        in 0..2 -> 0
        in 3..5 -> 3
        else -> 6
    }
    val tempY = when(y) {
        in 0..2 -> 0
        in 3..5 -> 3
        else -> 6
    }
    for (i in tempX until tempX + 3) {
        for (j in tempY until tempY + 3) {
            if (board[i][j] == value)
                return false
        }
    }
    return true
}