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

난이도 : GOLD II

문제링크 : https://www.acmicpc.net/problem/17136

문제해결 아이디어

• 색종이를 0,0 ~ 9,9 까지 순차대로 탐색한다.
• 만약 1을 만나면 5~1 까지 덮을수 있는 색종이를 덮고 재귀함수를 실행한다.
• 재귀함수의 종료조건은 색종이를 덮은 횟수가 기존의 횟수보다 많을경우, 더이상 탐색할 필요가 없으므로 종료.
• 9,9 까지 끝까지 탐색을 완료한경우
• 크기별로 색종이가 5개씩 존재하는데 색종이를 다 사용하는 경우 해당크기의 색종이는 넘어간다.

소스코드

import sys

input = sys.stdin.readline
# 색종이를 순회하면서 1을 만나면 1~5 중에 덮어지는 색종이를 dfs 탐색한다.
# 색종이 개수가 0이면 continue
# 최소 개수 출력
board = []

for _ in range(10):
    board.append(list(map(int, input().split())))

paper = [5] * 5 #색종이 개수

ans = 101

def check_paper(x, y, board, size): # 색종이를 덮을수 있는지 확인하는 함수
    for i in range(x, x + size + 1):
        for j in range(y, y + size + 1):
            if board[i][j] == 0:
                return False
    return True


def check_empty(board):# 1을 다 덮었는지 확인하는 함수
    for i in range(10):
        for j in range(10):
            if board[i][j] == 1:
                return False
    return True


def dfs(x, y, cnt):
    global ans
    if x == 9 and y == 10:
        if check_empty(board):
            ans = min(ans, cnt)
        return

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

    if cnt >= ans:
        return

    if board[x][y] == 0:
        dfs(x, y + 1, cnt)

    else:
        for i in range(4,-1,-1):  # (4,3,2,1,0)
            if paper[i] == 0: # 남은 색종이가 없으면
                continue

            if x + i >= 10 or y + i >= 10:  # 색종이가 종이를 뚫고 나가는지
                continue

            if check_paper(x, y, board, i):
                for a in range(x, x + 1 + i):
                    for b in range(y, y + 1 + i):
                        board[a][b] = 0
                paper[i] -= 1
                dfs(x, y + 1, cnt + 1)
                for a in range(x, x + 1 + i):
                    for b in range(y, y + 1 + i):
                        board[a][b] = 1
                paper[i] += 1

dfs(0,0,0)

print(-1) if ans == 101 else print(ans)