[백준][코틀린][2580] 스도쿠

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

2580번: 스도쿠

문제 풀이

1. (0, 0) 을 처음으로 해서 완전 탐색을 한다. 

2. sudoku 배열의 sudoku[row][col] 값이 0인지 확인 한다.

2-1. 0일 경우 sudoku[row][col] 값이 넣을 수 있는 숫자를 1 부터 9까지 탐색하여 찾는다.

2-2. 탐색할 때 N-Queen 과 비슷한 로직을 이용하여 현재 기준이 되는 row, col 을 이용하여 같은 열에 동일한 숫자가 있는 지 확인하고

같은 행에 동일한 숫자가 있는 지 확인 한다.

2-3. 대각선의 경우 작은 3X3 사각형을 기준으로 동일한 숫자가 있는 지 확인 한다.

3. 0이 아닐 경우 이미 숫자가 채워져 있으므로 다음 열을 탐색 한다.

4. 탐색할 열이 9일 경우 다음 행을 탐색한다.

5. 탐색할 행이 9일 경우 모두 탐색을 완료 했으므로 실행을 종료한다. 이때 프로그램을 완전 종료해야지 백준 문제를 패스할 수 있다.

코드

import java.io.*
import kotlin.system.exitProcess

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sudoku = Array(9) { IntArray(9) }
    repeat(9) { index ->
        sudoku[index] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }

    dfs(sudoku, 0, 0)
}

private fun dfs(sudoku: Array<IntArray>, row: Int, col: Int) {
    //var r = row

    if (col == 9) {
        dfs(sudoku, row + 1, 0)
        return
    }

    if (row == 9) {
        // 결과 출력
        val sb = StringBuilder()

        for (i in 0..8) {
            for (j in 0..8) {
                sb.append("${sudoku[i][j]} ")
            }
            sb.append("\n")
        }

        println(sb.toString())
        exitProcess(0)
    }

    if (sudoku[row][col] == 0) {
        // 넣을 수 있는 Value 를 찾는다.
        for (i in 1..9) {
            if (check(sudoku, row, col, i)) {
                sudoku[row][col] = i
                dfs(sudoku, row, col + 1)
                sudoku[row][col] = 0
            }
        }
    } else {
        dfs(sudoku, row, col + 1)
    }
}

private fun check(sudoku: Array<IntArray>, row: Int, col: Int, number: Int): Boolean {
    // 같은 열에 number 와 같은게 있는 지 확인 한다.
    for (i in 0..8) {
        if (sudoku[row][i] == number) return false
    }

    // 같은 향에 number 와 같은게 있는 지 확인 한다.
    for (i in 0..8) {
        if (sudoku[i][col] == number) return false
    }

    // 주어진 row, col 이 속한 3X3 작은 사각형을 탐색하여 같은 숫자가 있는 지 확인한다.
    val r = (row / 3) * 3
    val c = (col / 3) * 3
    for (i in r..r +2) {
        for (j in c..c + 2) {
            if (sudoku[i][j] == number) return false
        }
    }

    return true
}