Uknow's Lab.
article thumbnail

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

 

17136번: 색종이 붙이기

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

www.acmicpc.net

 

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

 

 

1. 설명

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

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

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

 

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

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

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

 

 

 

2. 소스코드

<kotlin />
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 증가시킵니다.

profile

Uknow's Lab.

@유노 Uknow

인생은 Byte와 Double 사이 Char다. 아무말이나 해봤습니다.