백준 2239 스도쿠 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/2239

2239번: 스도쿠

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

알고리즘 분류

• 구현
• 백트래킹

풀이

2021.11.10 - [알고리즘 문제 풀이/백준] - 백준 2580 스도쿠 c++, Kotlin (백트래킹)

한 달 전에 c++로 풀었던 문제와 동일하다.

기억이 새록새록 나서 1트만에 풀어서 기분이 좋다.

윗글에도 입출력만 바꿔서 Kotlin  코드를 추가해줬다.

 

풀이는 이전 글을 참고하면 되기 때문에, 간단히만 설명하면,

문제 조건 그대로 스도쿠는 3*3크기의 박스, 가로, 세로줄에 1~9중 겹치는 숫자가 있으면 안 된다.

이 조건을 검사하기 위해 sqaure, row, col 세 개의 Array(9) {BooleanArray(10)}의 2차원 배열을 만든다.

이후 입력 받을 때 9의 square, row, col에 들어간 숫자를 true 처리해주면 되는데, row의 인덱스와 col의 인덱스를 다루긴 쉽지만, square는 ((r/3)*9+c)/3 혹은 (r / 3) * 3 + c / 3 로 인덱스를 찾아주어야 한다. 이 식으로 직접 r과 c를 통해 인덱스를 구해보면 이해할 수 있을 것이다.

 

이후 백트래킹을 이용한 dfs를 돌리는데, r과 c를 1차원 인덱스 idx로 만들어서 총 0~81을 탐색하게 만든다.

이렇게 1차원 인덱스를 이용하여 불필요한 범위를 제거할 수 있다.

1~9의 숫자중에 square, row, col에 없는 숫자가 있다면 해당 칸에 숫자를 넣고 다음 0인 칸을 찾아서 탐색을 진행한다.

만약 이 dfs의 줄기가 스도쿠를 완성시킬 수 없다면 다시 위로 돌아간다.(다른 숫자를 넣어볼 수 있는 칸까지 넣어왔던 숫자를 다시 0으로 되돌리며 돌아간다.)

인덱스가 81이 된다면 스도쿠가 완성됐다는 의미로 탐색을 종료한다.

사전 순 오름차순 정렬은 그냥 1부터 9, 순서대로 탐색하면 된다.

코드

val br = System.`in`.bufferedReader()
//사전 순으로 앞서는 것을 출력 -> 행 박스 열 순이 유리
//위 설명 x 그냥 순서를 1부터 9까지 탐색함으로써 자동으로 사전순 정렬
val square =  Array(9) { BooleanArray(10) }
val row =  Array(9) { BooleanArray(10) }
val col =  Array(9) { BooleanArray(10) }
var finish = false
//backtracking
fun play(idx : Int, graph : Array<CharArray>){

    var idxCopy = idx
    var r = 0
    var c = 0
    while(idxCopy<81){
        r = idxCopy/9
        c = idxCopy%9
        if(graph[r][c]=='0')
            break
        idxCopy++
    }

    if(idxCopy==81){
        finish= true
        return
    }

    for (i in 1..9) {
        //해당 칸에 숫자가 들어갈 수 없으면 다음 숫자 검사
        if (row[r][i]) continue
        if (col[c][i]) continue
        if (square[((r / 3) * 9 + c) / 3][i]) continue
        
        //들어갈 수 있다면 넣기
        graph[r][c] = (i + '0'.toInt()).toChar()
        row[r][i] = true
        square[((r / 3) * 9 + c) / 3][i] = true
        col[c][i] = true
        //다음 0인 칸 찾기
        play(idx + 1, graph)
        //이전 dfs에서 종료되었다면 싹 다 return으로 종료
        if (finish) return
        //해당 칸에 i를 넣고 다음 0들을 검사했을 때 스도쿠가 완성될 수 없다면 다시 초기화
        //return 이전에 넣으면그래프가 다시 초기화 됨에 유의
        graph[r][c] = '0'
        row[r][i] = false
        square[((r / 3) * 9 + c) / 3][i] = false
        col[c][i] = false
    }


}

fun main() = with(System.out.bufferedWriter()){
    //input
    val graph = Array(9){r->
        val line = br.readLine()
        for(c in 0 until 9){
            //row
            row[r][Character.getNumericValue(line[c])]=true
            //col
            col[c][Character.getNumericValue(line[c])]=true
            //square
            square[((r/3)*9+c)/3][Character.getNumericValue(line[c])]=true
        }
        line.toCharArray()
    }
    
    //solve
    play(0,graph)
    
    //answer
    for(i in 0 until 9){
        for(j in 0 until 9){
            write("${graph[i][j]}")
        }
        write("\n")
    }
    close()
}