문제

BOJ 17136: 색종이 붙이기 https://www.acmicpc.net/problem/17136

풀이

조건

• 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있다.
• 각 종류의 색종이는 5개씩 가지고 있다.
• 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다.
• 1이 적힌 칸은 모두 색종이로 덮여져야 한다.
• 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

풀이 순서

• 브루트포스로 종이를 붙일 수 있는 위치가 나올 때 까지 탐색한다.
• 종이를 붙일 수 있는 위치가 나오면 1 ~ 5의 종이 크기를 차례로 붙여본다.
• 종이를 붙일 수 있다면 붙인 뒤 백트래킹으로 다음 부분을 탐색한다.
• 끝까지 탐색이 끝나면 종이를 붙인 개수 중 최소값을 갱신한다.

코드

Python

import sys
sys.setrecursionlimit(10 ** 6)

paper = [list(map(int, sys.stdin.readline().split())) for _ in range(10)]
remain = [5, 5, 5, 5, 5]
total = 25


# 현재 종이 크기로 붙일 수 있는지 확인
def check(x, y, length):
    for i in range(x, x + length + 1):
        for j in range(y, y + length + 1):
            if paper[i][j] != 1:
                return False
    return True


def backtracking(r, c, paper_cnt):
    global remain, total

    # 종이 맨 밑 까지 도달 하면
    if r >= 10:
        total = min(total, paper_cnt)
        return
    
    # 종이 오른쪽 끝까지 가면 바로 아래 줄 부터 검사
    if c >= 10:
        backtracking(r + 1, 0, paper_cnt)
        return
    
    # 현재 위치에 종이 붙일 수 있으면
    if paper[r][c] == 1:
        # 종이 크기 1부터
        for k in range(5):
            # 현재 크기 종이를 이미 다 썼는지 확인
            if remain[k] == 0:
                continue
            # 현재 크기의 종이를 붙였을 때 범위 벗어나는지 확인
            if r + k >= 10 or c + k >= 10:
                continue
            
            # 중간에 0인 부분 나오는지 확인
            # 나오면 이 크기와 더 큰 종이는 못 붙임
            if not check(r, c, k):
                break
            
            # 해당 종이 크기를 붙인 상태로 갱신
            for i in range(r, r + k + 1):
                for j in range(c, c + k + 1):
                    paper[i][j] = 0
            # 현재 크기 개수 1 줄이기
            remain[k] -= 1

            # 다음 부분 탐색(오른쪽으로 다음 부분)
            backtracking(r, c + k + 1, paper_cnt + 1)
            
            # 다시 원상 복귀
            remain[k] += 1
            for i in range(r, r + k + 1):
                for j in range(c, c + k + 1):
                    paper[i][j] = 1
    # 현재 위치에 종이 못 붙이면 다음 칸(오른쪽) 확인
    else:
        backtracking(r, c + 1, paper_cnt)


backtracking(0, 0, 0)

print(-1 if total == 25 else total)

정리

• 100자리만 탐색하면 되기 때문에 브루트포스로 붙일 수 있는 위치를 탐색하며 백트래킹으로 몇 개의 종이를 붙일 수 있는지 확인하며 답을 구했다.