[BOJ/PYTHON] 17136. 색종이 붙이기

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

문제 요약

1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이를 5개씩 가지고 있음

10×10인 종이 중 1이 적힌 칸 위에 색종이를 붙일 때 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수

핵심 아이디어

색종이를 5개부터 4, 3, 2, 1 순으로 붙였다가 떼어서 다 구한다.

모든 칸을 다 체크하는데, 백트래킹 함수에 x, y 좌표값을 받았다. 종이를 붙일 수 있는지 체크하고, 붙일 수 있다면 색종이를 붙이고 남은 종이 개수가 담겨있는 리스트에서 1을 뺀다. 백트래킹으로 다음 걸 봐주고, 종이를 뗀다.

풀이

# gold2-17136. 색종이 붙이기

import sys
input = sys.stdin.readline

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

# 다음에 볼 게 0이 아닌지 체크 (색종이 붙일 수 있는지)
def check(y, x, length):
    for i in range(y, y + length + 1):
        for j in range(x, x + length + 1):
            if board[i][j] == 0:
                return False
    return True

# 색종이 붙임
def attach(y, x, length):
    for i in range(y, y + length + 1):
        for j in range(x, x + length + 1):
            board[i][j] = 0
    remain_papers[length] -= 1

# 색종이 붙였던 거 다시 돌려놓음
def remove(y, x, length):
    for i in range(y, y + length + 1):
        for j in range(x, x + length + 1):
            board[i][j] = 1
    remain_papers[length] += 1

def back(y, x, cnt):
    global answer
    # 끝까지 다 봄
    if y >= 10:
        answer = min(answer, cnt)
        return
    # 한 줄 다 봄 -> 다음 줄 보기
    if x >= 10:
        back(y + 1, 0, cnt)
        return

    # 색종이 붙이기
    if board[y][x] == 1:
        for length in range(5):
            # 범위 넘김
            if y + length >= 10 or x + length >= 10: continue
            # 종이 다 씀
            if not remain_papers[length]: continue            
            if check(y, x, length):
                attach(y, x, length)
                back(y, x + length + 1, cnt + 1)
                remove(y, x, length)    
    else: # 현재가 0이면 그 다음 오른쪽 거 확인
        back(y, x + 1, cnt)

back(0, 0, 0)

if answer != 26:
    print(answer) 
else: print(-1)

실행 시간

메모리 31268KB, 시간 1496ms (python3)