[파이썬 | BOJ | 17136] 색종이 붙이기

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을 출력한다.

풀이

처음 생각했을때는 그리디 알고리즘으로, 가장 큰 색종이를 붙일 수 있는대로 붙이는 것으로 생각했다.

그런데 그리디가 아니라 백트래킹으로 풀어야 한다. 처음 크다고 색종이를 붙이게 되면 1X1짜리가 많이 생겨서 색종이 수가 초과되게 된다.

 

따라서 현재 nowR, nowC에서 붙일 수 있는 가장 최대의 색종이 크기를 찾는다.

만약 현재 4X4색종이까지 붙일 수 있다면 4, 3, 2, 1짜리 색종이를 붙이는 것으로 백트래킹을 한다.

백트래킹 함수를 재귀호출하고 나면, 다시 색종이를 떼고 계속 반복한다.

 

현재 붙일 수 있는 색종이가 존재하지않지만 색종이가 남는다면 다음 칸으로 진행한다.

최소값 탐색이므로, 이미 사용한 색종이수가 현재 구한 최소값보다 커지면 바로 종료하면 된다.

 

최종적으로 마지막 칸에 왔을때 빈칸이 없으면 종료한다.