[BOJ] 17136 색종이 붙이기 (python)

색종이 붙이기 - BOJ

색종이 붙이기 - BOJ

def dfs(x, y, cnt):
    global ret
    if y >= 10:
        ret = min(ret, cnt)
        return
    if x >= 10:
        dfs(0, y + 1, cnt)
        return
    if a[x][y]:
        for p in range(5):
            if paper[p] == 5: # 5개 다 붙였으면 pass
                continue
            if x + p >= 10 or y + p >= 10: # 범위 넘어가면 pass
                continue
            flag = 0
            for i in range(x, x + p + 1):
                for j in range(y, y + p + 1):
                    if not a[i][j]: # 범위가 0이라면
                        flag = 1
                        break
                if flag: break
            if not flag: # 범위에 0이 없다면 (전부 1)
                for i in range(x, x + p + 1):
                    for j in range(y, y + p + 1):
                        a[i][j] = 0

                paper[p] += 1
                dfs(x + p + 1, y, cnt + 1) # 앞뒤로 전부 백트래킹 기법 (최소인 것만 갱신하고 원래 값으로 회복)
                paper[p] -= 1

                for i in range(x, x + p + 1):
                    for j in range(y, y + p + 1):
                        a[i][j] = 1
    else: # 1이 아니면 다음 x
        dfs(x + 1, y, cnt)

a = [list(map(int, input().split())) for _ in range(10)]
paper = [0, 0, 0, 0, 0]
ret = float('inf')
dfs(0, 0, 0)
if ret == float('inf'):
    print(-1)
else:
    print(ret)