글 읽기 - [Kotlin(JVM)] 스도쿠 타임아웃 질문

prunusnira 3년 전 0

백트래킹으로 해결하고자 했습니다

로컬로 테스트를 해봤을 때 각종 스도쿠 문제들을 대입했을 때도 풀이에는 문제가 없는것 같습니다

속도도 빠른편이구요

그러나 타임아웃이 발생하고 있습니다. (45%, 86%에서 발생)

로컬에서 테스트를 해봤을 때 (buffered reader/writer를 사용한 읽기/쓰기(flush) 파트 제외)

9*9를 모두 0으로 채운 경우 15ms 이내, 문제에서 제시하는 예시는 10ms 이내,

그리고 인터넷상에서 찾은 고난이도 스도쿠 문제들을 입력해도 150ms 이하로 답변이 나옵니다.

입출력 처리에 걸리는 시간을 고려해도 1초가 되지 않을것 같은데 무엇이 문제일까요?

그리고 이 문제와 관련하여 더 개선할 수 있는 방법이 있을까요? (백트래킹을 사용한 채로)

* 코드 설명

solve:

1) (i, j) 각 케이스에 대해 처리를 시작합니다. (i, j)의 값이 0이 아니라면 다음 칸으로 스킵합니다

2) 마지막 칸에 도달했다면 출력 후 종료합니다

find:

1) solve에서 (i, j)가 0이라면 가로/세로/3*3 범위내에서 중복되는 가용 숫자들을 찾아내고 각 케이스에 대해 다음 칸을 처리합니다

2) 가용 가능한 숫자가 없다면 리턴하고 이전단계로 되돌아갑니다

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.collections.ArrayList
import kotlin.system.exitProcess

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

fun main() {
    val arr = Array(9) { _ -> IntArray(9) { _ -> 0 } }
    for(i in 0 until 9) {
        arr[i] = br.readLine().split(" ").map(String::toInt).toIntArray()
    }
    br.close()

    solve(0, 0, arr)
}

/**
 * 1. (0, 0)에서 시작하여 각 칸을 탐색
 * 2. 값이 0인 (i, j)가 나오면 가로, 세로, 3*3 범위에서 가용 가능한 값을 탐색
 * 3. 각 탐색 결과에서 중복되는 값을 구함
 * 3-1. 중복되는 값이 없다면 이전 단계로 이동
 * 3-2. 중복되는 값에 대해 각각 대입하고 다음 칸으로 이동
 *
 * 케이스에서 오류가 확인되면 대입한 칸을 0으로 만들고 이전 단계로 이동함
 */
fun solve(i: Int, j: Int, arr: Array<IntArray>) {
    if(i < 9) {
        if(arr[i][j] != 0) {
            if(j < 8) solve(i, j+1, arr)
            else solve(i+1, 0, arr)
        }
        else {
            find(i, j, arr)
        }
    }
    else {
        // 결과 확인
        for(a in 0 until 9) {
            for(b in 0 until 9) {
                bw.write("${arr[a][b]}")
                if(b < 8) bw.write(" ")
            }
            if(a < 8) bw.write("\n")
        }
        bw.flush()
        bw.close()
        exitProcess(0)
    }
}

fun find(i: Int, j: Int, arr: Array<IntArray>) {
    val hlist = checkHr(j, arr)
    val wlist = checkWx(i, arr)
    val tlist = check33(i, j, arr)

    // 가로, 세로, 3*3에 대해 중복되는것만 모아서 solve를 돌림
    if(hlist.count() > 0 && wlist.count() > 0 && tlist.count() > 0) {
        val dup = ArrayList<Int>()
        for(a in 1..9) {
            if(hlist.contains(a) &&
                    wlist.contains(a) &&
                    tlist.contains(a)) {
                dup.add((a))
            }
        }

        if(dup.count() > 0) {
            for(v in dup) {
                arr[i][j] = v
                if(j < 8) solve(i, j+1, arr)
                else solve(i+1, 0, arr)
                arr[i][j] = 0
            }
        }
        else return
    }
}

fun checkHr(j: Int, arr: Array<IntArray>): ArrayList<Int> {
    val list = ArrayList<Int>(9)
    list.addAll(Array(9) { x -> x+1 })

    for(a in 0 until 9) {
        if(list.contains(arr[a][j])) list.remove(arr[a][j])
    }

    return list
}

fun checkWx(i: Int, arr: Array<IntArray>): ArrayList<Int> {
    val list = ArrayList<Int>(9)
    list.addAll(Array(9) { x -> x+1 })

    for(a in 0 until 9) {
        if(list.contains(arr[i][a])) list.remove(arr[i][a])
    }

    return list
}

fun check33(i: Int, j: Int, arr: Array<IntArray>): ArrayList<Int> {
    val list = ArrayList<Int>(9)
    list.addAll(Array(9) { x -> x+1 })

    var startx = if(i < 3) 0
    else if(i < 6) 3
    else 6

    var starty = if(j < 3) 0
    else if(j < 6) 3
    else 6

    for(a in startx until startx + 3) {
        for(b in starty until starty + 3) {
            if(list.contains(arr[a][b])) list.remove(arr[a][b])
        }
    }

    return list
}

fabi88 3년 전 0

find 함수가 너무 비대하여 시간 초과가 발생하는 것으로 보입니다.

특히 check 함수들에서 해당 범위를 만족하는지를 파악할 때 범위 전체를 기준으로 두기 보다

값 하나에 집중하여 1부터 9까지 숫자를 대입하여 보고 기준을 만족하는지 확인하여 채워 넣는 방향으로 구현하면 좋을 것 같습니다.

예를 들어 checkHr 함수는 아래와 같이 특정 값에 대해 조건을 만족하는지 확인하도록 변형할 수 있습니다.

이렇게 하면 불필요한 리스트 생성 및 리스트 검색/제거 과정이 사라져 속도 향상이 있을 것이라 생각됩니다.

fun checkHr(j: Int, num: Int, arr: Array<IntArray>): Boolean {
    for(a in 0 until 9) {
        if (arr[a][j] == num)
            return false
    }
    return true
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Kotlin(JVM)] 스도쿠 타임아웃 질문

prunusnira 3년 전 0

fabi88 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말