[백준 17136번] [Kotlin] 색종이 붙이기

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

17136번: 색종이 붙이기

 

난이도 : 골드 2
태그 : 브루트포스, 백트래킹

 

 

설명

처음엔 그리디적으로 생각해, 큰 색종이 부터 붙이면 되겠구나! 생각했으나,

6x6의 경우, 3x3 색종이를 쓸 경우 4장이면 가능한 것에 비해,

5x5를 쓸 경우, 5x5 색종이 한개와, 1x1 색종이 11장이 필요하기 때문에, 색종이 개수를 초과하여, 붙이는게 불가능합니다.

 

흠... 그리디는 아니겠고, 그럼 백트래킹 + 브루트포스인가? 생각했는데,

문제 지문을 다시 봤더니 색종이 크기가 10x10 밖에 안되길래,

모든 경우의 수를 다 확인해도 되겠다는 생각이 들어 백트래킹을 사용하기로 했습니다.

 

 

 

소스코드

import java.util.StringTokenizer

lateinit var map: Array<Array<Int>>
val pagerCnt = arrayOf(0, 5, 5, 5, 5, 5)
var result = Int.MAX_VALUE

fun main() = with(System.`in`.bufferedReader()) {
    map = Array(10) {
        val st = StringTokenizer(readLine())
        Array(10) { st.nextToken().toInt() }
    }

    backTracking(0, 0, 0)

    println(if (result == Int.MAX_VALUE) -1 else result)
}


fun backTracking(x: Int, y: Int, depth: Int) {
	// 모든 칸 탐색 완료
    if (x >= 10) {
        result = minOf(result, depth)
        return
    }

	// 현재 depth(사용한 종이 수)가 result 보다 크거나 같다면 탐색할 필요 없음
    if (depth >= result) return

	// 현재 칸이 1이라면?
    if (map[x][y] == 1) {
        paperAttach@ for (i in 5 downTo 1) {
            if (pagerCnt[i] == 0) continue

            // 색종이 붙일 수 있는지 확인
            for (dx in 0 until i) {
                for (dy in 0 until i) {
                	// for문 라벨링을 사용
                    if (x + dx >= 10 || y + dy >= 10 || map[x + dx][y + dy] == 0) continue@paperAttach
                }
            }


            attach(x, y, i, 0)
            pagerCnt[i]--
            if (y + i < 10) {
            	// 옆칸으로 이동
                backTracking(x, y + i, depth + 1)
            } else {
            	// 마지막 칸이라면 아랫 칸으로 이동
                backTracking(x + 1, 0, depth + 1)
            }
            pagerCnt[i]++
            attach(x, y, i, 1)
        }
    } else {
    	// 현재 칸이 0이라면 옆 칸으로 넘어감
        if (y + 1 < 10) {
            backTracking(x, y + 1, depth)
        } else {
            backTracking(x + 1, 0, depth)
        }
    }
}

// 색종이를 붙이는 함수
fun attach(x: Int, y: Int, size: Int, flag: Int) {
    repeat(size) { dx ->
        repeat(size) { dy ->
            map[x + dx][y + dy] = flag
        }
    }
}

 

y 좌표를 증가시키며 한 칸씩 이동하되, 끝에 도달하면

x좌표를 1칸 증가, y좌표를 0으로 만들어 아랫 칸으로 넘어갑니다.

이후, x가 10이 되면 탐색을 종료합니다.

 

색종이를 붙이는 과정에서,

현재 좌표가 1이라면 (map[x][y] == 1)

먼저, 색종이를 붙일 수 있는지 확인합니다.

색종이를 붙일 수 있는지 확인하는 방법은 그냥 단순히 현재 색종이 사이즈가 모두 1인지를 확인하는 방식으로 구현하였습니다.

색종이를 붙일 수 있다면 색종이를 붙이고, 사용한 색종이 개수를 1 감소시킵니다.

이후, 다시 자기 자신을 호출하고,

해당 탐색이 끝나면 색종이를 다시 떼고, 사용한 색종이 개수를 다시 1 증가시킵니다.