[Python] 백준 17136. 색종이 붙이기

문제

10x10 크기 종이의 각 칸에 0 또는 1이 쓰여있고 1이 쓰여있는 칸을 주어진 크기의 색종이를 이용해 덮어야 한다. 넘치거나 부족하게 덮어서는 안된다. 이 때 사용하는 색종이의 최소 개수를 구해야 하는 문제이다.

풀이

처음 생각난 방법은 그리디 알고리즘이었다. 근데 도저히 구현할 방법이 떠오르질 않아 못하겠더라.

조금 더 생각해보니 어차피 칸의 갯수는 100칸이고 이정도면 brute force로 돌 수 있겠더라.

각 칸을 탐색하다가 1이 쓰여진 칸을 만나면 그 위치를 기준으로 최대 5x5 크기의 색종이까지 붙일 수 있는지 보고, 붙일 수 있다면 붙인 후 다음 칸을 확인한다.이 때 만약 4x4 크기의 색종이까지 붙일 수 있다면 1x1, 2x2, 3x3, 4x4의 색종이를 모두 붙여봐야 한다.

백트래킹을 이용해 풀었고, 따라서 당연히 dfs도 된다.

check 함수는 현재 칸에서 1x1 ~ 5x5 크기의 색종이를 붙일 수 있는지 확인한다.
backtracking 함수는 각 좌표 하나하나를 탐색한다.
현재 보는 칸에 1이 쓰여있다면 5종류의 색종이를 하나씩 갖다 대보고 붙일 수 있다면 붙인 후 다음 칸으로 넘어간다.
현재 보는 칸에 0이 쓰여있다면 그대로 다음 칸으로 넘어간다.
종료조건은 꾸준히 증가시키던 y값이 종이의 크기인 10을 넘어갔을때다.

remain은 현재 쓸 수 있는 색종이가 몇개나 남았는지를 나타내는 배열이다. 사실 직관적으로 이해하려면 0번째 칸을 비우고 'remain[1]이 1x1 크기의 색종이가 몇개 남았는지를 본다' 라고 생각해야 하지만, 실제로 check 함수를 통해 붙일 수 있는 색종이의 크기를 계산할 때 +0이 1x1 크기의 색종이, +1이 2x2 크기의 색종이를 붙일 수 있는지 확인한다. 그래서 이게 더 편하더라.

코드

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

def check(y, x, offset):
  for i in range(y, y+offset+1):  
    for j in range(x, x+offset+1):
      if paper[i][j] != 1: return False
  return True

def backtracking(y, x, c):
  global remain, total
  if y >= 10:
    total = min(total, c)
    return
  if x >= 10:
    backtracking(y+1, 0, c)
    return
  if paper[y][x] == 1:
    for k in range(5):
      if remain[k] == 0: continue
      if y+k >= 10 or x+k >= 10: continue

      if not check(y, x, k): break
      for i in range(y, y+k+1):
        for j in range(x, x+k+1):
          paper[i][j] = 0
      remain[k] -= 1
      backtracking(y, x+k+1, c+1)
      remain[k] += 1
      for i in range(y, y+k+1):
        for j in range(x, x+k+1):
          paper[i][j] = 1
  else : backtracking(y, x+1, c)

backtracking(0, 0, 0)
print(-1 if total == 25 else total)