[Python/파이썬] 백준 17136번 색종이 붙이기

17136번: 색종이 붙이기

 

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

코드

board = []
for i in range(10):
    board.append(list(map(int, input().split())))

confeti = [0] * 6
ans = 26


def chk(r, c, l):
    for i in range(r, r+l):
        for j in range(c, c+l):
            if board[i][j] != 1:
                return False
    return True


def bt(r, c, cnt):
    global ans
    if c >= 10:
        bt(r+1, 0, cnt)  # 다음 행으로 넘어가기
        return
    if r >= 10:
        ans = min(ans, cnt)  # 끝까지 탐색
        return
    if board[r][c] == 1:
        for l in range(1, 6):
            if confeti[l] == 5:  # 이미 lXl 종이 다 씀
                continue
            if r+l-1 >= 10 or c+l-1 >= 10:  # 종이 붙이면 범위 넘어감
                continue
            if chk(r, c, l):
                for i in range(r, r+l):
                    for j in range(c, c+l):
                        board[i][j] = -1    # 종이 붙임
                confeti[l] += 1
                bt(r, c+l, cnt+1)
                confeti[l] -= 1
                for i in range(r, r+l):
                    for j in range(c, c+l):
                        board[i][j] = 1     # 종이 다시 떼기
    else:
        bt(r, c+1, cnt)


bt(0, 0, 0)
print(ans if ans < 26 else -1)

백트래킹을 이용하여 가능한 모든 경우의 수를 구해서 조건을 만족하는 최소값을 찾는다.

• chk 함수 : r, c에서 l × l 크기의 종이를 붙일 수 있는지 여부 판단
• bt 함수
  • 파라미터로 받은 c가 10 이상이면 열의 끝까지 탐색한 것이므로 다음행으로 넘어가서 탐색
  • 파라미터로 받은 r이 10 이상이면 탐색을 모두 끝마친 것이므로 ans에 min(ans, cnt)를 저장하고 리턴
  • board[r][c] == 1이면 종이를 붙일 수 있는 칸이므로 붙일 수 있는 종이를 붙이고 재귀적으로 탐색을 계속한다.

 

처음에는 백트래킹으로 하지 않고 그냥 그리디하게 붙일 수 있는 가장 큰 색종이 조각을 붙이게 했다. 그랬더니 아래와 같은 예제에서 틀렸다.

 

1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

 

위와 같은 경우가 있을 수 있기 때문에 탐색할 때 먼저 나오는 칸부터 무조건 큰 종이를 붙여주면 안된다. 그래서 모든 경우의 수를 다 살펴볼 수 있도록 백트래킹으로 풀이하였다.