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

 

2239번: 스도쿠

 

문제 이해 & 기본 개념

• 스도쿠를 완성시키는 문제
• 시간 제한이 2초로 충분하므로 백트래킹을 이용하면 쉽게 풀 수 있다.

---

중요 포인트

• 가로, 세로, 3x3 사각형에서 중복되는 숫자가 없는지 확인해야한다.
• 가로, 세로에선 아래와 같이 쉽게 확인할 수 있다.
  • map[x][y]와 for문의 위치가 같아지는 경우 continue로 처리해버리면, 세로의 경우를 체크하지 못할 수 있다.

    // map[x][y]와 중복되는 숫자가 있는지 체크하는 for문
    for (i in 0 until 9){
        if(map[x][i] == map[x][y]) if(i != y) return false // 가로
        if(map[i][y] == map[x][y]) if(i != x) return false // 세로
    }

• 3x3 사각형을 체크하기 위해선 (x,y)가 어느 사각형에 포함 되는지를 알아야한다.
• 아래 처럼 x,y에 대해 각각 getPosit() 메소드를 적용하면 어느 사각형에 포함 되는지 알 수 있다.

fun getPosit(p:Int):Int {
    return when(p){
        in 0 until 3 -> 0
        in 3 until 6 -> 3
        in 6 until 9 -> 6
        else -> -1
    }
}

    // 3x3 사각형에서의 중복 체크
    val startX = getPosit(x)
    val startY = getPosit(y)

    for (i in startX until  startX + 3){
        for (j in startY until startY + 3){
            if(i == x && j == y) continue
            if(map[i][j] == map[x][y]) return false
        }
    }

---

최종 풀이

• 먼저, 입력을 받음과 동시에 0인 곳의 위치를 리스트에 저장한다.
• 첫 번째 0부터 시작해서 1~9 중 스도쿠 조건을 만족하는 숫자를 넣고, 다음 0의 위치로 이동
• 9까지 다 넣었으면 해당 위치를 0으로 만든다.

fun solve(map:Array<StringBuilder>, zero:ArrayList<Pair<Int,Int>>, now:Int){
    if(zero.size == now){ // 모든 칸이 다 채워진 경우
        if(allCheck(map)){ // 스도쿠 조건을 모두 만족하는 경우
            map.forEach { println(it) }
            exitProcess(0) // 바로 프로그램 종료
        }
        else return // 다 채워졌지만, 스도쿠 조건이 만족되지 않는 경우
    }

    val cur = zero[now]
    for (i in 1 .. 9){
        map[cur.first][cur.second] = (i+48).toChar()

        val overlap = checkOverlap(map, cur.first, cur.second)
        if(overlap){ // 중복이 안되었으면
            solve(map, zero, now+1)
        }
    }
    map[cur.first][cur.second] = '0'
}

---

주의 할점

• 0의 위치에서 1~9까지 다 채운 후 그 자리를 0으로 돌려줘야한다.
• 헷갈려서 0으로 안 돌려 놓았다가 삽질했다..

---

소스 코드

import kotlin.system.exitProcess

/**
 * 중복이 있는지 체크하는 메소드
 */
fun checkOverlap(map:Array<StringBuilder>, x:Int, y:Int):Boolean {
    for (i in 0 until 9){
        if(map[x][i] == map[x][y]) if(i != y) return false
        if(map[i][y] == map[x][y]) if(i != x) return false
    }

    val startX = getPosit(x)
    val startY = getPosit(y)

    for (i in startX until  startX + 3){
        for (j in startY until startY + 3){
            if(i == x && j == y) continue
            if(map[i][j] == map[x][y]) return false
        }
    }

    return true
}

fun getPosit(p:Int):Int {
    return when(p){
        in 0 until 3 -> 0
        in 3 until 6 -> 3
        in 6 until 9 -> 6
        else -> -1
    }
}

fun allCheck(map:Array<StringBuilder>):Boolean{
    for (i in 0 until 9){
        for (j in 0 until 9){
            if(!checkOverlap(map, i,j)) return false
        }
    }
    return true
}

fun solve(map:Array<StringBuilder>, zero:ArrayList<Pair<Int,Int>>, now:Int){
    if(zero.size == now){
        if(allCheck(map)){
            map.forEach { println(it) }
            exitProcess(0)
        }
        else return
    }

    val cur = zero[now]
    for (i in 1 .. 9){
        map[cur.first][cur.second] = (i+48).toChar()

        val overlap = checkOverlap(map, cur.first, cur.second)
        if(overlap){ // 중복이 안되었으면
            solve(map, zero, now+1)
        }
    }
    map[cur.first][cur.second] = '0'
}

fun main(){
    val map = Array(9){StringBuilder()}
    val zero = arrayListOf<Pair<Int,Int>>()

    repeat(9){
        map[it].append(readln())
        map[it].forEachIndexed{idx, c->
            if(c == '0') zero.add(Pair(it, idx))
        }
    }

    solve(map, zero, 0)
}