백준 17136 색종이 붙이기 (파이썬)

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

17136번: 색종이 붙이기

큰 색종이부터 붙이는 방식을 먼저 생각했는데 예외 케이스가 있어서 브루트포스로 구현

 

1. a에 종이의 상태를 저장하고 paper에 다섯 종류의 색종이를 각각 몇 장 사용했는지 저장한다

2. (0, 0)부터 시작해서 a[x][y]가 1인 모든 좌표에서 크기 1~5인 색종이를 붙여가면서 모든 케이스를 확인해야 한다

3. x좌표가 범위를 넘어가면 (0, y+1)로 재귀한다

   y가 범위를 넘어가면 맨 끝까지 탐색한 것이므로 최소값을 갱신한다

4. a[x][y]가 0이면 (x+1, y)로 재귀한다

   1이면 크기 1부터 5까지 색종이를 붙일 수 있는지 확인한다

5. 만약 색종이 5장을 이미 붙였거나 범위를 벗어나는 크기의 색종이라면 continue한다

6. 색종이를 붙일 수 있는지 확인한다. 단순히 반복문으로 0이 있는지 검사하면 된다

7. 붙일 수 있으면 다시 반복문으로 색종이를 붙이는 칸의 숫자를 0으로 바꿔준다

8. paper를 증가시켜 주고 (x+k+1, y)로 재귀한다

   그다음에는 paper와 지운 칸을 다시 되돌려준다

import sys

input = sys.stdin.readline

def func(x, y, cnt):
    global ans
    if y >= 10:
        ans = min(ans, cnt)
        return

    if x >= 10:
        func(0, y+1, cnt)
        return

    if a[x][y] == 1:
        for k in range(5):
            if paper[k] == 5:
                continue
            if x + k >= 10 or y + k >= 10:
                continue

            flag = 0
            for i in range(x, x + k + 1):
                for j in range(y, y + k + 1):
                    if a[i][j] == 0:
                        flag = 1
                        break
                if flag:
                    break

            if not flag:
                for i in range(x, x + k + 1):
                    for j in range(y, y + k + 1):
                        a[i][j] = 0

                paper[k] += 1
                func(x + k + 1, y, cnt + 1)
                paper[k] -= 1

                for i in range(x, x + k + 1):
                    for j in range(y, y + k + 1):
                        a[i][j] = 1
    else:
        func(x + 1, y, cnt)


a = [list(map(int, input().split())) for _ in range(10)]
paper = [0 for _ in range(5)]
ans = sys.maxsize
func(0, 0, 0)
print(ans) if ans != sys.maxsize else print(-1)