[Python] Baekjoon - 17136. 색종이 붙이기

백준 17136번 문제 색종이 붙이기는 10x10 크기의 종이에 다양한 크기의 색종이를 붙이는 문제다. 필요한 색종이의 최소 개수를 구하는 문제인데, 백트래킹을 이용해서 색종이를 붙이는 모든 경우를 계산해서 답을 구할 수 있다. 난이도는 골드 2이다.

 

백준 17136번 색종이 붙이기 문제 정보

알고리즘 분류

- 백트래킹 및 브루트 포스

난이도

- 골드 2

 

색종이 붙이기 문제 요약

• 10x10 크기의 종이가 각 칸에 0 또는 1로 채워져 있으며, 1이 쓰인 칸에만 색종이를 붙일 수 있다.
• 색종이는 5x5, 4x4, 3x3, 2x2, 1x1 각각 5장씩 존재한다.
• 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수 구하라. 종이를 모두 못 채우면 -1을 반환한다.

 

문제 풀이 과정

• 처음에는 그리디 방식으로 앞에서부터 칸을 탐색하면서 각 칸에 붙일 수 있는 최대 크기의 색종이를 붙이려고 했으나, 더 나중에 등장하는 칸에 큰 색종이를 붙여야 하는 경우가 있어서 기각했다.
• 두 번째는 1인 칸마다 붙일 수 있는 최대 크기를 구해서, 내림차순으로 정렬하고 크기가 큰 색종이부터 붙이려고 했다. 그러나 무조건 큰 색종이를 붙이면 안 되는 경우가 있어서 실패했다.
• 아래의 예시는 4x4먼저 붙일 경우 1x1 색종이가 모자라게 된다.
  • 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 1 1 0 0 0
    0 0 1 1 1 1 1 0 0 0
    0 0 1 1 1 1 1 1 0 0
    0 0 1 1 1 1 1 1 0 0
    0 0 0 1 1 1 1 1 0 0
    0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    틀린 답: -1
    정답: 6 (3,3,2,1,1,1)
• 마지막으로는 백트래킹을 이용하여 각 칸에서 붙일 수 있는 모든 경우의 수를 수행하도록 하였다. 프루닝 조건은 지금까지 구한 최소 색종이 개수보다 커지면 return 한다.

 

코드

# (r, c)를 기준으로 붙일 수 있는 색종이의 최대 크기를 구하는 함수
def check_size(r, c):
    global board
    res = 1

    for d in range(1, 5):
        if r + d > 9 or c + d > 9:
            break

        size_up = True
        for row in board[r:r+d+1]:
            if row[c:c+d+1] != ['1' for _ in range(d+1)]:
                size_up = False
                break

        if size_up:
            res += 1
        else:
            break

    return res


# board에서 (r, c)를 기준으로 size만큼의 정사각형 범위를 num으로 채우는 함수
def fill(r, c, size, num):
    global board

    for rr in range(r, r+size):
        for cc in range(c, c+size):
            board[rr][cc] = num


# depth번째 1이 적힌 칸을 채우는 함수
def backtracking(depth, cnt):
    global board, paper, fill_area, min_cnt

    # 마지막칸까지 채우면 최소 색종이 개수 갱신
    if depth == len(fill_area):
        min_cnt = min(min_cnt, cnt)
        return

    # 지금까지 구한 최소 색종이 개수보다 커지면 종료
    if cnt >= min_cnt:
        return

    r, c = fill_area[depth]
    # 이전 칸에 의해 이미 채워졌으면 다음 칸으로 넘어가기
    if board[r][c] == '0':
        backtracking(depth+1, cnt)
        return
    size = check_size(r, c)

    # 현재 칸에 붙일 수 있는 색종이를 모두 붙여보기
    for s in range(size, 0, -1):
        if paper[s] > 0:
            fill(r, c, s, '0')
            paper[s] -= 1
            backtracking(depth+1, cnt+1)
            fill(r, c, s, '1')
            paper[s] += 1


def fill_board():
    global board, min_cnt

    backtracking(0, 0)

    if min_cnt == 30:
        return -1

    return min_cnt


if __name__ == '__main__':
    board = []
    paper = [0,5,5,5,5,5]
    fill_area = []
    min_cnt = 30

    for r in range(10):
        tmp = input().split()
        board.append(tmp)
        for c in range(10):
            if tmp[c] == '1':
                fill_area.append((r, c))

    print(fill_board())