[백준 2239번][Kotlin] 스도쿠

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

2239번: 스도쿠

 

난이도 : 골드 4
태그 : 구현, 백트래킹

 

 

설명

유명한 보드게임인 스도쿠를 기반으로 한 코테 문제입니다.

빈칸에 들어갈 수 있는 경우의 수를 하나씩 찾아 대입해보고,

최종적으로 결과값을 도출해내는 백트래킹 문제입니다.

DFS를 사용하여 풀이하였습니다.

 

 

소스코드

입력값 세팅

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.system.exitProcess

var map = Array(9) { Array(9) { 0 } }

data class Point(var x: Int, var y: Int)

val zeroPointArray = ArrayList<Point>()
var emptyCount = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    repeat(9) { x ->
        val line = br.readLine()
        repeat(9) { y ->
            map[x][y] = line[y].digitToInt()
            if (map[x][y] == 0) {
                zeroPointArray.add(Point(x, y))
            }
        }
    }
    emptyCount = zeroPointArray.size

    dfs(0)
}

 

Point는 좌표값 x, y를 담을 data class 이며,

map은 스도쿠의 보드 (9x9) 정보를 담을 배열입니다.

emptyCount는 빈칸의 개수, zeroPointArray는 빈 칸의 좌표를 담을 Point형 ArrayList입니다.

 

값을 받으면서, 빈칸(0)이면 하나씩 zeroPointArray에 추가합니다.

 

 

 

후보값 도출

fun findKeys(x: Int, y: Int): ArrayList<Int> {
    val nums = Array(10) { false }

    for (i in 0 until 9) {
        nums[map[x][i]] = true
    }
    for (i in 0 until 9) {
        nums[map[i][y]] = true
    }

    val squareX = when (x) {
        0, 1, 2 -> 0
        3, 4, 5 -> 3
        6, 7, 8 -> 6
        else -> -1
    }
    val squareY = when (y) {
        0, 1, 2 -> 0
        3, 4, 5 -> 3
        6, 7, 8 -> 6
        else -> -1
    }

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            if (i == x && j == y) continue
            nums[map[squareX + i][squareY + j]] = true
        }
    }

    val result = ArrayList<Int>()
    for (i in 1..9) {
        if (!nums[i]) result.add(i)
    }
    return result
}

 

x, y좌표가 주어지면 해당 좌표에 들어갈 수 있는 숫자를 return 해주는 메소드 입니다.

 

nums라는 boolean 배열을 사용하여 한 번 이상 등장한 숫자를 체크해주었습니다. (0은 버리고 1~9까지 사용)

 

 

 

 

 

for (i in 0 until 9) {
    nums[map[x][i]] = true
}
for (i in 0 until 9) {
    nums[map[i][y]] = true
}

 

가로와 세로에 있는 값들을 탐색하며 한 번 이상 등장한 숫자를 true로 바꿔줍니다.

 

 

 

 

 

 val squareX = when (x) {
     0, 1, 2 -> 0
     3, 4, 5 -> 3
     6, 7, 8 -> 6
     else -> -1
 }
 val squareY = when (y) {
     0, 1, 2 -> 0
     3, 4, 5 -> 3
     6, 7, 8 -> 6
     else -> -1
 }
 for (i in 0 until 3) {
     for (j in 0 until 3) {
         if (i == x && j == y) continue
         nums[map[squareX + i][squareY + j]] = true
     }
 }

 

해당 좌표가 포함된 3x3블럭을 탐색하는 부분입니다.

 

 

 

val result = ArrayList<Int>()
for (i in 1..9) {
    if (!nums[i]) result.add(i)
}
return result

최종적으로, nums 배열을 체크하며 값이 false인 값을 찾아 ArrayList에 담아 return 합니다.

 

 

 

백트래킹

fun dfs(depth: Int) {
    if (depth == emptyCount) {
        map.forEach { it ->
            it.forEach { it2 ->
                print(it2)
            }
            println()
        }
        exitProcess(0)
    }

    val point = zeroPointArray[depth]
    val foundKey = findKeys(point.x, point.y)

    for (i in 0 until foundKey.size) {
        map[point.x][point.y] = foundKey[i]
        dfs(depth + 1)
        map[point.x][point.y] = 0
    }
}

 

depth는 깊이, 즉 현재 채워진 빈칸의 개수를 의미합니다.

 

채워진 빈칸의 개수가 전체 빈칸의 개수와 같을 경우, map의 좌표를 출력 후

exitProcess(0) { 자바의 System.exit(0)과 같습니다)를 통해 프로그램을 종료시킵니다.

 

 

현재 깊이에 맞는 빈칸의 좌표와 findKeys 메소드를 사용하여,

해당 좌표에 들어갈 수 있는 후보값들을 도출합니다.

 

해당 값을 하나씩 대입하면서, dfs를 재귀적으로 호출합니다.

dfs탐색이 끝나면 해당 좌표를 다시 0으로 돌립니다.

 

 

스도쿠 퍼즐의 특성 상, 복수의 정답이 나올 수 있는데,

문제의 지문으로는 사전순으로 빠른 것을 출력하도록 요구하였습니다.

 

위 코드에서는 findKeys 메소드에서 애초에 사전순으로 후보값들을 전달해주기 때문에,

가장 처음 완성된 맵이 정답입니다.

 

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.system.exitProcess

var map = Array(9) { Array(9) { 0 } }

data class Point(var x: Int, var y: Int)

val zeroPointArray = ArrayList<Point>()
var emptyCount = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    repeat(9) { x ->
        val line = br.readLine()
        repeat(9) { y ->
            map[x][y] = line[y].digitToInt()
            if (map[x][y] == 0) {
                zeroPointArray.add(Point(x, y))
            }
        }
    }
    emptyCount = zeroPointArray.size

    dfs(0)
}

fun dfs(depth: Int) {
    if (depth == emptyCount) {
        map.forEach { it ->
            it.forEach { it2 ->
                print(it2)
            }
            println()
        }
        exitProcess(0)
    }

    val point = zeroPointArray[depth]
    val foundKey = findKeys(point.x, point.y)

    for (i in 0 until foundKey.size) {
        map[point.x][point.y] = foundKey[i]
        dfs(depth + 1)
        map[point.x][point.y] = 0
    }
}

fun findKeys(x: Int, y: Int): ArrayList<Int> {
    val nums = Array(10) { false }

    for (i in 0 until 9) {
        nums[map[x][i]] = true
    }
    for (i in 0 until 9) {
        nums[map[i][y]] = true
    }

    val squareX = when (x) {
        0, 1, 2 -> 0
        3, 4, 5 -> 3
        6, 7, 8 -> 6
        else -> -1
    }
    val squareY = when (y) {
        0, 1, 2 -> 0
        3, 4, 5 -> 3
        6, 7, 8 -> 6
        else -> -1
    }

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            if (i == x && j == y) continue
            nums[map[squareX + i][squareY + j]] = true
        }
    }

    val result = ArrayList<Int>()
    for (i in 1..9) {
        if (!nums[i]) result.add(i)
    }
    return result
}

 

 

 

 

후기

평소 스도쿠 퍼즐을 주로 하는데,

코딩테스트 문제로 이렇게 접하니 반가운 문제였네요.