17136: 색종이 붙이기

풀이 시간

• 1h 30m
• 좌표를 하나씩 이동하면서 backtracking을 수행하는 아이디어를 참고했다

구현 방식

• 좌표를 하나씩 이동하면서 backtracking을 수행하는 점이 신선했다

backtracking

• backtracking 함수의 인자는 x, y, count이다

• return 조건
  -> y좌표가 10 이상이면 모든 경우를 좌표를 탐색한 것이기 때문에 global min_count를 갱신해주고 return
  -> x좌표가 10이상이면 다음 y줄을 탐색해줘야하기 때문에 backtracking(0, y+1, count)를 호출해주고 return

• 탐색 조건

  • board[x][y] == 1 이라면 (해당 좌표에 색종이를 붙일 수 있다면) 1 ~ 5까지 for문을 돌면서 다섯 종류의 색종이의 경우를 고려해준다
    
    -> 해당 색종이를 모둔 다 사용한 경우 (paper[p] == 5) 또는 해당 색종이를 붙이게 되면 범위를 벗어나는 경우 (x+p > 10 or y+p > 10) continue
    
    -> board를 순회하면서 색종이를 붙일 수 있는 지 없는 지 판별해준다
    
    -> 만약 색종이를 붙일 수 있는 경우에는,
    1)색종이를 붙여주기(board에 표시)
    2)해당 색종이 사용 개수 +1
    3)backtracking(x+p, y, count+1)호출
    4)다시 해당 색종이 사용 개수 -1
    5)색종이 다시 떼기' 를 수행해준다

  • 만약 board[x][y] == 0이라면 다음 단계를 위해 backtracking(x+1, y, count)를 호출해준다

코드

import sys

def backtracking(x, y, count):
    global min_count

    # return 조건
    if y >= 10:
        min_count = min(min_count, count)
        return
    if x >= 10:
        backtracking(0, y+1, count)
        return
    
    if board[x][y] == 1:
        for p in range(1, 6):
            if paper[p] == 5: #해당 색종이를 모두 다 사용한 경우
                continue
            if x + p > 10 or y + p > 10: #범위를 벗어나는 경우
                continue

            possible = True
            for i in range(x, x+p): #색종이를 붙일 수 있는 지 없는 지 판별
                for j in range(y, y+p):
                    if board[i][j] == 0:
                        possible = False; break
                if not possible: break
            
            if possible:
                for i in range(x, x+p): #색종이 붙이기
                    for j in range(y, y+p):
                        board[i][j] = 0
                
                paper[p] += 1
                backtracking(x+p, y, count + 1)
                paper[p] -= 1

                for i in range(x, x+p): #색종이 다시 떼기 (for backtracking)
                    for j in range(y, y+p):
                        board[i][j] = 1
    else:
        backtracking(x+1, y, count)


board = []
for _ in range(10):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))
paper = [0 for _ in range(5 + 1)] #각 종류의 색종이는 5개씩 가지고 있다.

min_count = int(10e9)
backtracking(0, 0, 0)
if min_count == int(10e9): print(-1)
else: print(min_count)

결과