[BOJ 17136] 색종이 붙이기(Python)

---

문제

색종이 붙이기

---

문제 해설

10X10 행렬이 주어지고 1x1, 2x2, ... 5x5 색종이를 각각 최대 5장씩 사용하여 행렬을 모두 0으로 만드는 문제입니다. 여기서 색종이를 붙이려면 해당 영역이 모두 1이어야 붙일 수 있습니다.

저는 총 3개의 메소드를 활용했습니다.

• 전체 탐색 메소드
• 현재 좌표에서 사용할 수 있는 색종이를 구하는 메소드
• 현재 좌표로부터 색종이를 붙여, 해당 영역을 모두 0 또는 1로 바꾸는 메소드

우선 전체 탐색 메소드에서 1을 찾게되면 해당 구역에서 사용할 수 있는 색종이를 모두 구합니다. 그 다음 색종이를 붙이고(==그래프를 모두 0으로 만들고) 재귀 호출을 합니다.

재귀 호출이 끝난뒤엔 붙였던 색종이를 떼어 냅니다.(== 그래프를 다시 1로 만듭니다.)

이렇게 붙일 수 있는 색종이가 없거나 모든 구역을 색종이로 메꾸게 되면 종료합니다.

가장 중요한 점은, 1을 발견하면 재귀호출 뒤에 바로 함수를 종료시켜야 한다는 점입니다. 그렇지 않으면 정답을 구하는 과정에서 전체탐색으로 인한 중복때문에 시간 복잡도가 터지게 됩니다.

---

풀이 코드

import sys

input = sys.stdin.readline
graph = [list(map(int, input().split())) for _ in range(10)]
paper = [0, 5, 5, 5, 5, 5]
answer = 30
# 현 좌표에서 사용할 수 있는 색종이가 무엇인지 판별
def possible(x, y):
    number = []
    for n in range(1, 6):
        for i in range(x, x + n):
            for j in range(y, y + n):
                # 0이 발견되면 그 뒤에 색종이도 못쓴다.
                if i < 0 or i >= 10 or j < 0 or j >= 10 or graph[i][j] == 0:
                    return number
        number.append(n)
    return number


# 그래프 색칠하기.
# 좌표, 윈도우 크기, 어떤 값으로 색칠할지
def colored(x, y, n, value):
    for i in range(x, x + n):
        for j in range(y, y + n):
            graph[i][j] = value


# 백트래킹 탐색
def dfs(blank):
    global answer
    # 빈공간이 없으면
    if blank == 0:
        answer = min(answer, 25 - sum(paper[1:]))
        return
    for i in range(10):
        for j in range(10):
            if graph[i][j] == 1:
                # 붙일 수 있는 모든 색종이의 크기
                number = possible(i, j)
                for num in number[::-1]:
                    # 색종이가 있으면 붙이고 재귀
                    if paper[num] > 0:
                        paper[num] -= 1
                        colored(i, j, num, 0)
                        dfs(blank - (num ** 2))
                        paper[num] += 1
                        colored(i, j, num, 1)
                return


temp = 0  # 공간 세기
for i in range(10):
    for j in range(10):
        if graph[i][j] == 1:
            temp += 1
dfs(temp)
print(answer) if answer != 30 else print(-1)

---