17136. 색종이 붙이기 (Python)

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

풀이

 1이 적힌 칸에서 1x1 크기의 색종이부터 5x5 크기의 색종이까지 붙일 수 있는지를 체크한다. 색종이를 붙이고 나면 색종이로 덮어진 부분을 체크해주고 다음 1이 적힌 칸으로 넘어가서 색종이를 붙일 수 있는지를 체크하는 과정을 반복한다. 모든 1이 적힌 칸을 색종이로 덮고 나면 사용한 색종이의 개수들을 비교하여 그 중 최소 개수를 기록하면 된다.

 

코드

# size * size 색종이를 붙일 수 있는지 체크하는 함수
def sizeCheck(idx, size):
    x, y = oneList[idx]

    # 범위가 넘어가는 경우는 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):
            if board[i][j] != 1 or checked[i][j]:  # 붙일 수 없으면 False 리턴
                return False

    return True  # 붙일 수 있으면 True 리턴


# checked 리스트에 flag 값(Ture 또는 False) 설정
def checkVisit(idx, size, flag):
    x, y = oneList[idx]

    for i in range(x, x+size):
        for j in range(y, y+size):
            checked[i][j] = flag


# (1 위치 인덱스, 1x1 색종이 개수, 2x2 색종이, 3x3 색종이, 4x4 색종이, 5x5 색종이, 총 색종이 개수, 남은 1의 개수)
def solve(idx, p1, p2, p3, p4, p5, pCnt, leftOne):
    # print(p1, p2, p3, p4, p5, pCnt, leftOne)
    if leftOne == 0:  # 1을 전부 색종이로 덮었다면 res 갱신
        global res
        res = min(res, pCnt)
        return

    x, y = oneList[idx]
    if checked[x][y]:  # 이미 색종이로 덮어진 부분이면 다음 인덱스로 넘어간다.
        solve(idx + 1, p1, p2, p3, p4, p5, pCnt, leftOne)
        return

    if sizeCheck(idx, 1) and p1 + 1 <= 5:  # 1x1 색종이를 사용하여 덮을 수 있는 경우
        checkVisit(idx, 1, True)  # 덮었음을 체크 해주고
        solve(idx + 1, p1 + 1, p2, p3, p4, p5,
              pCnt + 1, leftOne - 1)  # 다음으로 넘어간다
        checkVisit(idx, 1, False)  # 백트래킹

    if sizeCheck(idx, 2) and p2 + 1 <= 5:  # 2x2 색종이를 사용하여 덮을 수 있는 경우
        checkVisit(idx, 2, True)
        solve(idx + 1, p1, p2 + 1, p3, p4, p5, pCnt + 1, leftOne - 4)
        checkVisit(idx, 2, False)

    if sizeCheck(idx, 3) and p3 + 1 <= 5:  # 3x3 색종이를 사용하여 덮을 수 있는 경우
        checkVisit(idx, 3, True)
        solve(idx + 1, p1, p2, p3 + 1, p4, p5, pCnt + 1, leftOne - 9)
        checkVisit(idx, 3, False)

    if sizeCheck(idx, 4) and p4 + 1 <= 5:  # 4x4 색종이를 사용하여 덮을 수 있는 경우
        checkVisit(idx, 4, True)
        solve(idx + 1, p1, p2, p3, p4 + 1, p5, pCnt + 1, leftOne - 16)
        checkVisit(idx, 4, False)

    if sizeCheck(idx, 5) and p5 + 1 <= 5:  # 5x5 색종이를 사용하여 덮을 수 있는 경우
        checkVisit(idx, 5, True)
        solve(idx + 1, p1, p2, p3, p4, p5 + 1, pCnt + 1, leftOne - 25)
        checkVisit(idx, 5, False)


if __name__ == '__main__':
    board = [[0 for _ in range(10)] for _ in range(10)]
    checked = [[False for _ in range(10)] for _ in range(10)]  # 색종이로 덮인 부분인지 체크
    oneCount = 0  # 보드에서 1의 총 개수
    oneList = []  # 1로 되어있는 위치 리스트
    res = float('inf')

    for i in range(10):
        tmp = list(map(int, input().split()))
        for j in range(10):
            if tmp[j] == 1:
                oneCount += 1
                board[i][j] = 1
                oneList.append((i, j))

    solve(0, 0, 0, 0, 0, 0, 0, oneCount)

    if res == float('inf'):
        print(-1)
    else:
        print(res)