[백준] 17136번 - 색종이 붙이기 (파이썬)

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

# 색종이 붙이기
import sys
import copy
input = sys.stdin.readline
MAX = sys.maxsize

N = 10
arr = []
length_one = 0
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] == 1:
            length_one += 1
paper = [5] * 6
paper[0] = 0
result = MAX


def check(x, y, nx, ny, arr):
    possible = True
    if 0 <= nx <= N and 0 <= ny <= N:
        for i in range(x, nx):
            for j in range(y, ny):
                if arr[i][j] == 0:
                    possible = False
                    break
            if not possible:
                break
    else:
        possible = False
    return possible


def dfs(a, b, arr, count, delete):
    global result
    if delete == length_one:
        result = min(result, count)
        return
    # 모든 배열을 탐사
    for x in range(a, N):
        for y in range(N):
            # 만약 해당 부분이 1이면
            if arr[x][y] == 1:
                # 사용가능한 종이 고르기
                for p in range(0, len(paper)):
                    if paper[p] == 0:
                        continue
                    # 종이의 범위만큼 지정
                    nx = x + p
                    ny = y + p
                    # 만약 해당 범위가 전부 1이면
                    if check(x, y, nx, ny, arr):
                        # 종이 붙이기
                        d = 0
                        temp = copy.deepcopy(arr)
                        for i in range(x, nx):
                            for j in range(y, ny):
                                temp[i][j] = 0
                                d += 1
                        paper[p] -= 1
                        dfs(x, y, temp, count+1, delete+d)
                        paper[p] += 1
                return


dfs(0, 0, arr, 0, 0)
if result == MAX:
    print(-1)
else:
    print(result)

 

백트랙킹

1. 입력을 받으면서 1의 개수를 저장한다 (arr, length_one)

2. paper = [0, 5, 5, 5, 5, 5] : 1x1 종이 수부터 5x5종이 수를 배열에 저장

3. dfs(x좌표, y좌표, 전체배열, 사용종이수, 삭제한 1의 개수)

    - 전체 배열을 돌면서 해당 부분이 1이면 사용할 종이를 선택 (사용가능한 종이의 수가 0이면 continue)

    - 해당 종이의 범위내부가 전부 1인지 체크 (check함수)

    - arr을 deepcopy한 temp를 가지고 1을 지워나간다 (d = 현재 지운 0의 개수)

    - 종이 사용횟수 1감소, dfs(x좌표,y좌표,현재배열(temp),사용한 종이수(count+1),삭제한 1의 개수(delete+d))호출

    - 삭제한 1의개수 (delete)가 총 1의 개수 (length_one)과 같으면 result에 최솟값 저장

4. result 출력

 

무작정 풀기 시작해서 뭔가 복잡하다

중간에 가독성이 너무 떨어져서 check함수를 만들고 주석을 넣어줬다..