[백준] 17136 색종이 붙이기, python

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

 

 

 

좌측상단에서 처음 1이 나오는 위치를 찾는다. 그리고 그 위치부터 크기가 5인 색종이부터 붙인다. 한 종류의 색종이의 개수가 5를 넘거나 더 이상 붙일 수 없으면 색종이의 크기를 1 줄여서 탐색한다. 이 경우 항상 최소개수를 만족하게 된다.

 

 

import sys
import copy
input = sys.stdin.readline

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

answer = float('inf')

cnt = [0]*5

# 좌측상단에서 처음으로 1이 나오는 위치
def findPos():
    for x in range(10):
        for y in range(10):
            if board[x][y]:
                return x,y
    return None

# i,j로부터 t*t의 색종이를 놓을수 있는지 여부
def valid(i,j,t):
    if i+t>=10 or j+t>=10:
        return False
    for x in range(t+1):
        for y in range(t+1):
            if not board[i+x][j+y]:
                return False
    return True

# i,j번째 위치에 t*t색종이를 배치하거나 제거하는 함수
def putPaper(i,j,t,val):
    for x in range(t+1):
        for y in range(t+1):
            board[i+x][j+y] = val

def dfs(used):
    global answer
	
    # 기존 방법보다 사용한 색종이 양이 많으면 탐색하지 않는다
    if used >= answer:
        return
	
    # 1이 없다면(모두 붙였다면)
    pos = findPos()
    if not pos:
        answer = used
        return 

    i,j = pos
    for t in range(4,-1,-1):
        if cnt[t] >= 5:
            continue
        if valid(i,j,t):
            putPaper(i,j,t,0)
            cnt[t] += 1
            dfs(used+1)
            putPaper(i,j,t,1)
            cnt[t] -= 1
            
dfs(0)

print(-1 if answer == float('inf') else answer)