[BOJ][Python] 백준 17136번: 색종이 붙이기

1일 1PS 63일차!

📚 문제

---

골드 2 색종이 붙이기

💡 풀이 과정

---

• dfs 를 사용해 모든 경우의 수를 찾아볼 수 있다.
• 1 인 경우 사용가능한 모든 크기의 색종이를 모두 DFS 진행한 이후에 다시 복원시킨다.

📌포인트

---

• 함수형태의 DFS 는 해당 시점에서의 board 를 사용하기 때문에 매번 copy 해서 같이 보낼 필요가 없다..!
• DFS 이기 때문에 해당 시점에서 DFS 를 호출해서 끝까지 갔다가 다시 돌아오면서 board 를 복원시킨다면 정상적으로 board 를 사용할 수 있다.
• board 를 수정하면 다음번 수행에서 충돌이 일어나지 않는가? 에 찝찝한 의구심이 있었지만 해당 풀이과정을 따라가다보면 모든 board 는 다음번 수행 전 모두 복구되는 것을 확인할 수 있다.

💻 코드

---

board = [list(map(int, input().split())) for _ in range(10)]
max_cnt = 25
paper = [5, 5, 5, 5, 5]


def dfs(x, y, c):
    global max_cnt, paper

    if x >= 10:
        max_cnt = min(max_cnt, c)
        return max_cnt

    if y >= 10:
        dfs(x + 1, 0, c)
        return

    if board[x][y] == 1:
        for i in range(5):
            if paper[i] == 0:
                continue
            if y + i >= 10 or x + i >= 10:
                continue

            if not cal_paper(i, x, y):
                break

            for j in range(i + 1):
                for k in range(i + 1):
                    board[x + j][y + k] = 0

            paper[i] -= 1
            dfs(x, y + i + 1, c + 1)

            paper[i] += 1
            for j in range(i + 1):
                for k in range(i + 1):
                    board[x + j][y + k] = 1
    else:
        dfs(x, y + 1, c)


def cal_paper(i, x, y):
    for j in range(i + 1):
        for k in range(i + 1):
            if board[x + j][y + k] != 1:
                return False
    return True


dfs(0, 0, 0)
print(-1 if max_cnt == 25 else max_cnt)