[종만북] 6.5 재귀호출과 완전탐색[게임판 덮기]

게임판 덮기 문제는 3칸짜리 블록을 H x W 의 보드에 몇 가지의 방법으로 맞출수 있는지 구하는

경우의 수 문제이다.

블록은 총 4가지 모양인데 ㄱ, ㄴ, ┌,  ┘  이런 모양으로 되어있다.

 

사고 과정

0. 블록이 들어가는 갯수가 3의 배수가 아니면 0을 리턴

1. 특정 지점 row와 col에서 위 4가지 모양에 대한 위치를 구하는 배열을 구한다.

2. 해당 모양에 대한 조건이 일치하면 블록을 그리고 일치하지 않으면 다음을 진행

3. 기존 상태를 복구하여 다른 모양일때를 구한다.

4. 모든 맵이 블록으로 꽉차면 리턴한다.

 

이렇게 사고과정을 하였고 구현을 진행했다.

그런데 구현중에 값이 너무 크게 나와 뭔가 잘못됐다는 걸 느꼇다.

나는 한 블록을 그리고 다음 블록을 그릴 위치를 구할때 i와 j를 0부터 시작해서 그리게 했다.

그러나 이렇게 하다보니 같은 위치에 또 그려지는 중복으로 그리게 되는 문제가 있었다.

그래서 종만북을 참고하여 해당 부분을 수정하고 답을 구하게 되었다.

 

기존 코드

 

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

    for (i in 0..c - 1) {
        val input = br.readLine().split(" ")
        val r = input[0].toInt()
        val c = input[1].toInt()
        val map = Array(r) { Array(c) { ' ' } }
        var count = 0
        for (j in 0..r - 1) {
            val ch = br.readLine()
            ch.forEachIndexed { index, ch ->
                map[j][index] = ch
                if (ch == '.') count++
            }
        }
        if (count % 3 != 0) {
            println(0)
            continue
        }
        println(boardCover(map))
    }
}

fun boardCover(map: Array<Array<Char>>): Int {

    var res = 0
    var isComplete = true
    var r = -1
    var c = -1
    for (i in 0..map.size - 1) {
        for (j in 0..map[i].size - 1) {
            if (map[i][j] == '.') {
                isComplete = false
                r = i
                c = j
                break
            }
        }
        if (isComplete == false) break
    }

    if (isComplete) return 1

    val firstR = arrayOf(0, -1, 0, 0)
    val firstC = arrayOf(1, 0, -1, -1)
    val secondR = arrayOf(1, 0, 1, -1)
    val secondC = arrayOf(0, 1, 0, 0)

    for (i in r..map.size - 1) {
        for (j in c..map[i].size - 1) {

            for (k in 0..3) {
                val firstDR = i + firstR[k]
                val firstDC = j + firstC[k]
                val secondDR = i + secondR[k]
                val secondDC = j + secondC[k]
                if (firstDR > -1 && firstDR < map.size && firstDC > -1 && firstDC < map[i].size &&
                    secondDR > -1 && secondDR < map.size && secondDC > -1 && secondDC < map[i].size
                ) {
                    if (map[i][j] == '.' && map[firstDR][firstDC] == '.' && map[secondDR][secondDC] == '.') {
                        map[i][j] = '*'
                        map[firstDR][firstDC] = '*'
                        map[secondDR][secondDC] = '*'
                        res += boardCover(map)
                        map[i][j] = '.'
                        map[firstDR][firstDC] = '.'
                        map[secondDR][secondDC] = '.'

                    }
                }

            }
        }
    }


    return res
}

 

 

수정된 코드

 

import java.io.BufferedReader
import java.io.InputStreamReader


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

    for (i in 0..c - 1) {
        val input = br.readLine().split(" ")
        val r = input[0].toInt()
        val c = input[1].toInt()
        val map = Array(r) { Array(c) { ' ' } }
        var count = 0
        for (j in 0..r - 1) {
            val ch = br.readLine()
            ch.forEachIndexed { index, ch ->
                map[j][index] = ch
                if (ch == '.') count++
            }
        }
        if (count % 3 != 0) {
            println(0)
            continue
        }
        println(boardCover(map))
    }
}

fun boardCover(map: Array<Array<Char>>): Int {

    var res = 0
    var isComplete = true
    var r = -1
    var c = -1
    for (i in 0..map.size - 1) {
        for (j in 0..map[i].size - 1) {
            if (map[i][j] == '.') {
                isComplete = false
                r = i
                c = j
                break
            }
        }
        if (isComplete == false) break
    }

    if (isComplete) return 1

    val firstR = arrayOf(0, 1, 0, 1)
    val firstC = arrayOf(1, 0, 1, 0)
    val secondR = arrayOf(1, 1, 1, 1)
    val secondC = arrayOf(0, 1, 1, -1)

    for (k in 0..3) {
        val firstDR = r + firstR[k]
        val firstDC = c + firstC[k]
        val secondDR = r + secondR[k]
        val secondDC = c + secondC[k]
        if (firstDR > -1 && firstDR < map.size && firstDC > -1 && firstDC < map[r].size &&
            secondDR > -1 && secondDR < map.size && secondDC > -1 && secondDC < map[r].size
        ) {
            if (map[r][c] == '.' && map[firstDR][firstDC] == '.' && map[secondDR][secondDC] == '.') {

                map[r][c] = (k + 48).toChar()
                map[firstDR][firstDC] = (k + 48).toChar()
                map[secondDR][secondDC] = (k + 48).toChar()
                res += boardCover(map)
                map[r][c] = '.'
                map[firstDR][firstDC] = '.'
                map[secondDR][secondDC] = '.'

            }
        }
    }


    return res
}

 

종반북을 참고한 코드

 

반영예정

 

 

혹시나 위 내용이 저작권법에 위반된다면 바로 내리겠습니다.

감사합니다.