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

---

solution.py

import sys
input = sys.stdin.readline

n = 10
graph = [list(map(int, input().split())) for _ in range(n)]
papers = [0,5,5,5,5,5] # 각 색종이 개수

# 색종이를 붙일 수 있는지 확인
def checkarr(x,y,size):
    for i in range(x,x+size):
        for j in range(y,y+size):
            if 0<=i<n and 0<=j<n and graph[i][j] == 1:
                pass
            else:
                return False
    return True

# 색종이를 붙이거나 떼기
def updatepaper(x,y,size,method):
    # 붙였을 경우 0으로 떼는 경우 1로
    for i in range(x, x+size):
        for j in range(y, y+size):
            graph[i][j] =  method
            
result = 25
# 완전탐색 dfs
def dfs(cnt):
    global result
    
    if cnt > result:
        return
    
    F = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1:
                x,y = i,j
                F = 1
                break
        if F ==1 :
            break
        
    # 1이 더이상 없을 경우
    if F == 0:
        if cnt < result:
            result = cnt
        return
    
    for size in range(5,0,-1): # 5부터 1까지 색종이 size
        if papers[size]>0 and checkarr(x,y,size):
            updatepaper(x,y,size,0)
            papers[size] -= 1
            dfs(cnt+1)
            updatepaper(x,y,size,1)
            papers[size] += 1

dfs(0)
if result == 25:
    print(-1)
else:
    print(result)

---

출처

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

17136번: 색종이 붙이기