악곱 == 악성곱슬

백트래킹

---

이 문제는 10x10 보드에 색종이를 붙여보는 문제이다.

색종이는 각각 5개씩 있고 크기는 1x1 ~ 5x5 이다.

1이 써져있는 곳에만 색종이를 붙여야 한다.

이때 붙일 수 있는 최소 색종이의 개수를 구해야한다.

그래서 나는, 우선 메모리에 무엇을 저장해야 하는가부터 생각했다.

1. 10x10 보드
2. 색종이 담은 배열

그리고 어떻게 풀어나가야 할지 고민했다. 재귀를 이용하여 구현했다.

1. 백트래킹 시작
   1. 만약 모든 공간이 0이면 최소값을 업데이트 하고 종료
   2. 만약 이전 최소값 보다 현재 값이 더 크다면 종료
2. 1이 있는 위치를 찾아서 5부터 1까지 붙여본다. (순서는 큰 상관이 없는 것 같지만, 큰게 안 될 확률이 높으므로 큰 것 부터 제거해나가는 방식으로 생각했다)
3. 색종이를 붙인 부분을 0으로 변경하고 카운트도 -1 한다음에 1로 돌아간다.
4. 모든 색종이를 소모했을 때 1이 남아있다면 -1을 출력하도록 한다.

구현

---

나는 처음에 시간초과가 떳다. 위 알고리즘에서 1-2에 해당하는 “이전 최소값보다 현재 값이 더 크다면 종료”라는 가지치기 조건을 빼먹었기 때문이다.

백트래킹에서 이와 같이 최소값을 구할 때는 좋은 테크닉인듯 싶다.

import sys

def check(x, y, size, papers):
    # 색종이가 없는 경우
    if papers[size] == 0:
        return False
    # 보드 범위를 넘어가는 경우
    if x + size > 10 or y + size > 10:
        return False
    for i in range(x, x+size):
        for j in range(y, y+size):
            # 색종이로 0인 공간은 채울 수 없음
            if board[i][j] == 0:
                return False
    return True

def all_zero():
    for i in range(10):
        for j in range(10):
            if board[i][j] == 1:
                return False
    return True

def set_number(x, y, size, num):
    for i in range(x, x+size):
        for j in range(y, y+size):
            board[i][j] = num

def backtrack(papers):
    global answer
    # 판이 모두 0이면 answer
    if all_zero():
        answer = min(answer, 25-sum(papers))
        return
    if 25-sum(papers) > answer:
        return
    # 1의 위치를 찾음
    x, y = -1, -1
    for i in range(10):
        if x > -1:
            break
        for j in range(10):
            if board[i][j] == 1:    # 앞에서 all zero 를 검사했기에 무조건 나옴
                x, y = i, j
                break
    for size in range(len(papers)-1, 0, -1):
        if check(x, y, size, papers):
            set_number(x, y, size, 0)
            papers[size] -= 1

            backtrack(papers)

            papers[size] += 1
            set_number(x, y, size, 1)
    return

def solution():
    papers = [0, 5, 5, 5, 5, 5]
    backtrack(papers)

if __name__ == "__main__":
    board = []
    answer = 26
    for _ in range(10):
        board.append(list(map(int, sys.stdin.readline().rstrip().split())))
    solution()
    print(answer if answer < 26 else -1)