[6개월 안에 백준 플래티넘 달성하기] 19. 스도쿠 2239

 

스도쿠

2239번: 스도쿠

 

문제

 

풀이

처음에 문제를 딱 보았을 때 막막하고 내가 모르는 어떤 수학 공식으로 풀어야 되는 건가 싶기도 하였습니다.

하지만 다행히도 해당 문제는 스도쿠의 크기가 9로 제한되어 있습니다. 따라서 가장 단순하게 모든 경우를 따져서 완전한 스도쿠를 만들어주기만 하면 됩니다.

 

0의 위치에 알맞은 숫자를 넣었다가 알맞은 숫자가 아니면 도로 빼줘야 되기 때문에 백트래킹 방식으로 코드를 구현해 주면 됩니다.

9의 제곱승의 시간 복잡도를 가지고 있기 때문에 시간초과가 날 것이라 생각하였습니다. 하지만 해당 문제의 경우 최초의 스도쿠만 구하면 되기 때문에 실제로는 얼마 안 되는 계산을 가집니다.

 

 

이때 0의 위치값만 따로 빼서 백트래킹을 돌려줘야 코드를 구현하기 쉽습니다. 처음에 이런 방식으로 구현하지 않았다가 코드가 너무 복잡해져서 다시 풀게 되었습니다.

// 0의 위치만 배열에 담아줌
for (i in 0 until 9) {
    for (j in 0 until 9) {
        if (arr[i][j] == 0) {
            zeroPos.add(Pos(i,j))
        }
    }
}

 

 

이제 각 위치에 어떤 숫자가 들어올 수 있는지 체크를 해줘야 합니다.

스도쿠의 룰에 맞춰서 행에서 체크, 열에서 체크, 그리고 칸에서 체크를 해주면 됩니다.

 

이때 체크해 주는 방법이 2가지가 있습니다. 

첫 번째로 일반 Boolean 배열을 사용하는 방법이 있고 두 번째로 비트마스크를 사용하는 방법이 있습니다.

비트마스크 방식이 조금 더 메모리를 절약할 수 있지만 백준에서 돌렸을 때는 크게 차이가 나지 않았습니다.

 

 

먼저 이해하기 간편한 Boolean 배열을 사용한 코드입니다.

fun 스도쿠_다른풀이() = with(System.`in`.bufferedReader()){

    val arr = Array(9) {readLine().map { it.toString().toInt() }.toIntArray()}

    data class Pos(val y: Int, val x: Int)
    val rows =  Array(9) { BooleanArray(10)}
    val cols = Array(9) { BooleanArray(10)}
    val kans = Array(9) { BooleanArray(10)}
    val zeroPos = arrayListOf<Pos>()

    for (i in 0 until 9) {
        for (j in 0 until 9) {
            if (arr[i][j] == 0) {
                zeroPos.add(Pos(i,j))
            } else {
                val num = arr[i][j]
                rows[i][num] = true  // i열에 num 숫자 방문 처리
                cols[j][num] = true  // j행에 num 숫자 방문 처리
                kans[(i/3*3) + (j/3)][num] = true  // i,j에 해당되는 칸에 num 숫자 방문 처리
            }
        }
    }

    var check = false
    fun solve(index: Int) {

        // 이미 스도쿠를 구했다면 바로 리턴
        if (check) return

        // 스도쿠가 완성된 경우
        if (index == zeroPos.size) {
            check = true
            arr.forEach { println(it.joinToString("")) }
            return
        }

        val pos = zeroPos[index]


        for (num in 1..9) {
            
            // 행, 열, 칸 셋 중 하나라도 존재하는 숫자인 경우 continue
            if (rows[pos.y][num] || cols[pos.x][num] || kans[(pos.y/3*3) + (pos.x/3)][num]) continue

            // 방문 처리
            arr[pos.y][pos.x] = num
            rows[pos.y][num] = true
            cols[pos.x][num] = true
            kans[(pos.y/3*3) + (pos.x/3)][num] = true

            solve(index+1)

            // 방문 처리 복구
            arr[pos.y][pos.x] = 0
            rows[pos.y][num] = false
            cols[pos.x][num] = false
            kans[(pos.y/3*3) + (pos.x/3)][num] = false
        }
    }
    solve(0)
}

 

 

비트마스크는 방문처리하는 숫자가 작을 경우 사용하기 좋은 알고리즘입니다.

아래 예시를 보시면 이해하기 편하실 겁니다.

1열의 스도쿠는 다음과 같다 
[0 0 2 0 3 4 0 7 9 ]
	따라서 1열에 빈 공간에는 9,7,4,3,2 이 사용 불가능하다
	이를 이진수 1010011100 로 표현할 수 있다. (각 자리수를 1처리)

1과 0의 의미 별 의미 
    - 1 : 이미 사용중
    - 0 : 사용 가능
    
더 나아가 [0 0 2 0 3 4 0 7 9 ] 에서 [5 0 2 0 3 4 0 7 9 ]로 5를 추가할 경우
	- 5 또한 사용 처리를 해줘야 한다.
	- 1010011100 or 100000 = 1010111100
    
반대로 다시 5를 뺄 경우
	- 5를 사용처리에서 빼줘야 한다.
	- 1010111100 xor 100000 = 1010011100

 

비트마스크를 사용한 풀이입니다. 

fun main() = with(System.`in`.bufferedReader()){

    val arr = Array(9) {readLine().toCharArray()}

    data class Pos(val y: Int, val x: Int)
    val rows = IntArray(9)
    val cols = IntArray(9)
    val kans = IntArray(9)
    val zeroPos = arrayListOf<Pos>()

    for (i in 0 until 9) {
        for (j in 0 until 9) {
            if (arr[i][j] -'0' == 0) {
                zeroPos.add(Pos(i,j))
            } else {
                val bit = 1 shl (arr[i][j] -'0')
                rows[i] = rows[i] or bit  // 동일하게 비스마스크 방식으로 방문처리
                cols[j] = cols[j] or bit
                kans[(i/3*3) + (j/3)] = kans[(i/3*3) + (j/3)] or bit
            }
        }
    }

    var check = false
    fun solve(index: Int) {
        if (check) return
        if (index == zeroPos.size) {
            if (!check) {
                check = true
                arr.forEach { println(it.joinToString("")) }
            }
            return
        }

        val pos = zeroPos[index]
        for (i in 1..9) {

            var bit = 1 shl i

            // 열과 행과 칸 모두 존재하지 않는 숫자일 경우
            if (rows[pos.y] and bit == 0 && cols[pos.x] and bit == 0 && kans[(pos.y/3*3) + (pos.x/3)] and bit == 0) {

                // 방문 처리
                arr[pos.y][pos.x] = '0' + i
                rows[pos.y] = rows[pos.y] or bit
                cols[pos.x] = cols[pos.x] or bit
                kans[(pos.y/3*3) + (pos.x/3)] = kans[(pos.y/3*3) + (pos.x/3)] or bit

                solve(index+1)

                // 방문 처리 복구
                rows[pos.y] = rows[pos.y] xor bit
                cols[pos.x] = cols[pos.x] xor bit
                kans[(pos.y/3*3) + (pos.x/3)] = kans[(pos.y/3*3) + (pos.x/3)] xor bit
            }
        }
    }
    solve(0)
}