백준 17136 색종이 붙이기 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

백트래킹 문제이다.

이전엔 이런 문제 보기만 해도 스트레스 받았는데, 이젠 그냥그냥 푼다.

처음엔 그냥 백트래킹없이 그리디하게 왼쪽 위부터 탐색해서 54321순으로 스티커를 붙이면서 넘어갔는데,

이렇게 하면 5번 예제를 통과하지 못한다.

즉 그냥 그리디하게 풀면 틀리고, 해당 칸에 5짜리, 3짜리, 1짜리 스티커를 붙일 수 있다고 하면 모두 붙여봐야 하는 것이다. 따라서 완전탐색(dfs)로 풀어야 하는데, 이것도 그냥 풀면 시간 초과가 나오니 가지치기를 해줘야 한다.

 

우선 2차원의 좌표는 1차원 인덱스로 바꾸어주고, 99까지 그래프의 값이 1인 칸을 찾는다.

1인 칸을 발견한다면 그 좌표에 대해 5,4,3,2,1 스티커를 붙여보고, 재귀를 한 단계 더 들어간다.

재귀로 들어가서 끝까지 탐색하고 다시 돌아오면 붙였던 스티커를 떼준다.

즉, 어떠한 좌표에 5,4,3,2,1 스티커 중 붙일 수 있는 스티커를 붙여보고 넘어가기,

안 붙이고 넘어가기 모두 탐색하는 것이다.

붙이기, 떼기, 붙일 수 있는지 확인하는 함수는 짜기 쉬우니 패스하고,

가지치기할 요소는 다음과 같다.

 

1. 현재 백트래킹 함수의 cnt가 answer(최솟값)보다 크다면 더 이상 탐색해도 최솟값을 찾을 수 없다.

2. 현재 좌표가 1인데 5,4,3,2,1 스티커를 모두 붙일 수 없다면, 현재 방식으론 모든 1에 스티커를 붙일 수 없다.

ex) 1짜리 스티커만 붙일 수 있는데 1짜리 스티커를 이미 5개 사용한 경우

 

백트래킹 함수가 호출될 때마다 스티커를 붙일 다음 위치(idx)를 찾아야 하는데, idx가 그래프를 벗어난다면 현재 그래프에 남은 1이 없다는 의미로 answer를 갱신하고 리턴하면 된다.

 

아직 이해가 안 됐다면

주석을 달아놨으니 코드를 보고 이해해보자.

 

코드

import java.util.*
const val INF = 987654321
val br = System.`in`.bufferedReader()
var answer=INF
val graph = Array(10){CharArray(10)}
val sticker = IntArray(6)

//스티커 붙일 수 있는지 확인
fun check(r : Int, c : Int, i : Int) : Boolean{
	//5개 사용한 스티커는 사용 불가
    if(sticker[i]==5)
        return false
    for(rr in 0 until i) {
        for (cc in 0 until i) {
            val nr = r + rr
            val nc = c + cc
            if (nr !in 0 until 10) return false
            if (nc !in 0 until 10) return false
            if (graph[nr][nc] != '1') return false
        }
    }
    return true
}

//스티커 붙이기, 떼기
fun stick(r : Int, c : Int, i : Int, mode : Int){
    sticker[i]+=mode
    for(rr in 0 until i) {
        for (cc in 0 until i) {
            val nr = r + rr
            val nc = c + cc
            if(mode==1){
                graph[nr][nc]='2'
            }
            else{
                graph[nr][nc]='1'
            }
        }
    }
}

fun backTracking(i : Int, cnt : Int){

	//현재 답보다 큰 경우 탐색 필요 x
    if(cnt>=answer) return

	var idx = i
    while(idx<=99 && graph[idx/10][idx%10]!='1'){
        idx++
    }
    
    //종료 조건
    //idx가 100이면 그래프에 1이 없음을 의미
    if(idx==100){
        answer= answer.coerceAtMost(cnt)
        return
    }

		//현재 idx를 r,c로 치환
        val r = idx / 10
        val c = idx % 10

		//5개 모두 붙일 수 없다면 더 깊이 탐색할 필요 없음
        var canMake=false
        for (i in 5 downTo 1) {
            if (check(r, c, i)) {
                stick(r, c, i, 1)
                backTracking((idx + 1), cnt + 1)
                stick(r, c, i, -1)
                canMake=true
            }
        }
        if(!canMake) return
}

fun main() = with(System.out.bufferedWriter()){
    for(i in 0 until 10){
        val tk = StringTokenizer(br.readLine())
        for(j in 0 until 10){
            graph[i][j] = tk.nextToken()[0]
        }
    }
    backTracking(0,0)

    if(answer==INF)
        answer = -1
    write("$answer")
    close()
}