[백준 17136] 색종이 붙이기 (python)

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

17136번: 색종이 붙이기

색종이 붙이기 문제

10x10 종이 위에 색종이들을 붙일 때 필요한 최소 개수를 구하는 문제

 

#사용 알고리즘

백트래킹(Backtracking)

반응형

📌문제 접근 포인트

1. 기본적으로 1x1, 2x2, 3x3, 4x4, 5x5의 색종이 5개씩 주어지므로 리스트에 5개씩 할당해 주자. 이때, 최대 결과값은 색종이를 모두 사용하는 25이므로 결과값의 최대치는 26만 잡아도 충분하다.

2. 반복 탐색을 통해 색종이를 붙여가면서 가능한 경우의 수 중 색종이를 최소로 사용해야한다. 이를 위해 백트래킹을 구상해 보자.

3. 2차원 배열을 탐색해 보자. 전체 칸 중 1인 부분에서만 백트래킹을 이용해 체크하도록 구성해 주자. 모든 색종이를 대조해 보면서 추가 조건으로 색종이가 남았는지 여부와 밖으로 나갔는지를 체크해줘야 한다.

4. 유망 조건을 따져보자. 이때의 유망 조건은 색종이를 붙일 수 있는지가 유망 조건이다.

5. 색종이를 붙일 수 있다면 색종이를 붙이고, 사용한 색종이를 차감해 주자. 이와 동시에 사용한 색종이 개수(p)를 늘려주는 식으로 백트래킹을 구성하자

6. 마지막으로 결과 값이 최소에 해당하는지 비교하면 쉽게 구성할 수 있다.

⚙ 내가 푼 정답 코드

def promise(a1, a2, b1, b2): #유망 조건
    for i in range(a1, a2+1):
        for j in range(b1, b2+1):
            if not paper[i][j]:
                return False
    return True

def attach(a1, a2, b1, b2, w): # 색종이 붙이기/떼기
    for i in range(a1, a2+1):
        for j in range(b1, b2+1):
            paper[i][j] = w

def glue(p):
    global result
    for y in range(10):
        for x in range(10):
            if paper[y][x]:
                for c in range(5):
                    ny, nx = y + c, x + c
                    if confetti[c] and ny < 10 and nx < 10 : # 색종이가 남았고 범위안에 있으면
                        if promise(y, ny, x, nx): 
                            attach(y, ny, x, nx, 0)
                            confetti[c] -= 1
                            glue(p+1) # 백트래킹
                            confetti[c] += 1
                            attach(y, ny, x, nx, 1)
                return
    result = min(result, p)

import sys
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(10)]
confetti = [5, 5, 5, 5, 5]
result = 26
glue(0)
if result == 26:
    print(-1)
else:
    print(result)