[백준/17136/파이썬] 색종이 붙이기

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

17136번: 색종이 붙이기

Problem

정사각형 모양을 한 다섯 종류의 색종이(1*1,2*2,3*3,4*4,5*5)를 10*10 종이 위에 붙이려고 한다. 1이 적힌 모든 칸을 붙이는데 필요한 색종이 최소 개수를 구해보자.

조건

색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐서 붙일 수 없다.

또, 칸의 경계와 일치하게 붙여야한다.

 

SOL)

처음에 그리디로 접근해볼까? 라는 생각이 드는 문제였다.

일단, 큰 것 부터 붙여가면서, 점차 크기를 줄여서 붙여가면 되지않을까? 했지만, 종이의 최소 개수를 구해야하기 때문에,

8*8의 색종이가 있는 경우, 4*4 4장이면 해결 되지만, 5*5 1장을 먼저 붙여버리면, 최소 개수가 만족하지 못함.

즉, 모든 경우 중에서, 특정 조건이 만족하는지 안하는지 봐야하는데, 경우의 수가 너무 많아서, 적당히 Pruning을 해야하는 Backtracking 문제라고 볼 수 있다.

 

Backtracking을 어떻게 구현할까 ?

 

1. if board == 1 : 종이를 크기 별로 붙이기 시작.
   • 종이를 붙이는 과정
     1. 크기가 5인 papers 배열에, 붙인 종이의 갯수를 기록해줄거임. 갯수 5개가 넘으면, 해당 종이는 넘어가고, x+k or y+k 즉, 종이가 경계선을 넘어가게 되서 못붙이는 경우도 해당 크기의 종이는 넘어감.
     2. 종이를 붙이는건, 해당 지점으로부터, 종이의 크기 만큼, 단순히 중간에 0이 있냐 없냐로 판단해줄거임. 0이 중간에 있다면, 붙이지 못하므로, 이 경우도 그냥 Pass.
     3. 만약, 붙일 수 있다면, 일단 붙여보고(붙였으니, 1이였던곳은 다 0으로), 우리는 지금 (0,0~9,9)까지 탐색을 진행하고 있으므로, 행은 그대로 냅두고, 종이의 크기만큼, 열을 옮겨줘서 탐색을 계속 진행할거임.
     4. 그 다음, 이렇게 했을 때, 최소의 갯수가 안될 수 도 있기 때문에, 다시 떼는 작업도 만들어 놓을거임.
     5. 재귀의 탈출 지점은, y>=10, 즉 모든 행을 다 돌았을 때, ans에 최솟값을 갱신 시켜줄거고, 모든 열을 다 돌았을 때는, 다음 행의 0열 부터 탐색을 진행(재귀함수 부르고, return).
2. if board == 0 : 다음 열로 재귀.

import sys
input =sys.stdin.readline
sys.setrecursionlimit(10**6)

board = [list(map(int,input().split())) for _ in range(10)]
papers =[0]*5 

#print(board)
ans= 26

def check(y,x,size):
    for i in range(y,y+size+1):
        for j in range(x,x+size+1):
            if board[i][j] ==0:
                return False
    return True

def backtracking(y,x,cnt):
    global ans
    
    if y>=10:
        ans=min(ans,cnt)
        return
    if x>=10:
        backtracking(y+1,0,cnt)
        return
    
    if board[y][x] ==1:
        for k in range(5):
            if papers[k] ==5:
                continue
            if y+k >=10 or x+k>=10:
                continue
            
            flag=check(y,x,k)
            
            if flag:
                for i in range(y,y+k+1):
                    for j in range(x,x+k+1):
                        board[i][j] =0
                papers[k] +=1
                backtracking(y,x+k+1,cnt+1)
                papers[k] -=1
                for i in range(y,y+k+1):
                    for j in range(x,x+k+1):
                        board[i][j] = 1
    else:
        backtracking(y,x+1,cnt)

backtracking(0,0,0)

print(ans if ans != 26 else -1)