백준[2580] - 스도쿠 (Kotlin)

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {

    var isFinished = false
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val board = Array<MutableList<Int>>(9) { mutableListOf() }

    for (i in 0 until 9) {
        board[i] = br.readLine().split(" ").map { it.toInt() }.toMutableList()
    }

    fun valid(i: Int, j: Int, num: Int): Boolean {
        // 행에 대해 겹치는 수 확인
        for (col in 0 until 9) {
            if (board[i][col] == num) return false
        }

        // 열에 대해 겹치는 수 확인
        for (row in 0 until 9) {
            if (board[row][j] == num) return false
        }

        // 3x3에 대해 겹치는 수 확인
        val startI = i - (i % 3)
        val startJ = j - (j % 3)
        for (row in startI until startI+3) {
            for (col in startJ until startJ+3) {
                if (board[row][col] == num) return false
            }
        }
        return true
    }

    fun dfs(i: Int, j: Int) {
        var newI = i
        var newJ = j
        if (j >= 9) {
            newI ++
            newJ = 0
        }
        if (newI >= 9) {
            for (k in 0 until 9) {
                for (l in 0 until 9) {
                    bw.write("${board[k][l]} ")
                }
                bw.write("\n")
            }
            isFinished = true
            return
        }

        // 현 위치가 0이 아닐 경우 바로 다음 dfs 수행
        if (board[newI][newJ] != 0) {
            dfs(newI, newJ+1)
        } else {
            // 처음 위치부터 1~9까지 모두 넣어보며 bfs 수행
            for (num in 1..9) {
                // 해당 값이 invalid라면 continue
                if (!valid(newI, newJ, num)) continue

                // valid라면 해당 값 넣음
                board[newI][newJ] = num
                // 다음 칸으로 이동
                dfs(newI, newJ+1)
                // 값 찾으면 종료
                if (isFinished) return
                // 다음 칸에서 답을 찾지 못했다면 다시 값 되돌려놓음
                board[newI][newJ] = 0
            }
        }
    }

    dfs(0, 0)

    bw.flush()
    br.close()
    bw.close()
}

 

입력된 9x9 보드의 값을 2차원 배열 형태로 저장한다.

i와 j에 대해 9x9 보드의 끝에 도달한 경우 결과를 출력하고 종료한다.

모든 보드의 칸을 순회하며 0(채워 넣어야 할 칸)일 경우 1~9까지 모든 값을 넣어본다.

이 때, valid 함수를 만들어 값을 넣기 전에 행, 열, 3x3에 대한 비교를 수행하여 1~9까지의 값에 대한 유효성을 검사한다.

유효성이 확인되지 않을 경우 다음 숫자로 넘어가고, 확인 될 경우 해당 숫자를 넣고 dfs를 통해 다음 칸으로 진행한다.

 

 

 

고찰 : 백트래킹을 집중적으로 공부 중인데, 여전히 비슷한 유형의 문제임에도 불구하고 허둥지둥댄다.

모든 백트래킹 문제가 같은 조건을 주지 않기에, 바뀐 조건에 대한 해결 방식이 슥슥 떠오르지가 않는 것이 시간을 많이 지체한다.

많은 문제를 풀어보면서 백트래킹의 공통된 패턴을 몸에 익히고 그 기본 지식을 바탕으로 변형되는 조건에 대해 여유롭게 생각할 수 있는 숙련도가 필요할 것 같다.

 

걸린 시간 : 40분

난이도 : 골드 4

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

2580번: 스도쿠