[Algorithm] BaekJoon : 17136. 색종이 붙이기 by Python

[문제 바로가기] https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

📌문제 설명

아래 그림과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

색종이를 크기가 10×10인 종이 위에 붙이려고 한다.

종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다.

1이 적힌 칸은 모두 색종이로 덮여져야 한다.

색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다.

또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

 

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

 

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

---

💡 문제 풀이

간만에 좋은 문제를 풀었다. (= 쉽지 않았다.😂)

 

반례를 쉽게 찾지 못해서 많이 헤맸던 문제였다.

A형 기출문제 답게 완전탐색 + 재귀(가지치기)로 해결하였다.

 

문제를 해결한 과정은 다음과 같다.

 

step 0)
먼저, 변수 및 함수를 선언한다.

 

변수

• papers : 입력 배열(10x10)
• used : 색종이 종류별 사용 가능한 개수를 알려주는 배열
• answer : 최소 색종이 개수를 담을 변수
• one : papers에서 1의 개수 → one의 값이 0이면 바로 '0'을 출력한다.

함수

• recursive : 재귀를 진행하면서 최소 색종이를 찾는 함수
  인자는 one, cnt 두 가지가 있다.
  one : 1의 개수
  cnt : 색종이 사용 개수
• check : 변경 가능한 부분인지 파악하기 위한 함수

재귀 종료 조건은 다음과 같다.

1. 색종이를 모두 덮으면(즉, one이 0이면) 종료한다.
2. 사용한 색종이가 이전 최소값보다 크면 종료한다.
3. 모든 색종이를 사용했을 경우 종료한다.

step 1)
재귀 함수(recursive) 진행은 입력값으로 주어지는 10 x 10 배열의 좌표로 진행한다.
→ (0,0)부터 (9,9)까지

 

step 2)
step 1)에서 탐색하려고 선정한 좌표가 1이면(= 색종이로 바꿀 수 있으면) 5가지 색종이 종류에 대해 변경이 가능한지 파악한다.

 

step 3)
변경이 가능하면 해당 크기의 색종이로 바꾸고 다음 재귀를 진행한다.

 

이 때, 큰 크기의 색종이를 먼저 사용하는 것이 최선은 아니기 때문에 덮은 색종이를 다시 원래대로 복구시켜서 다음 재귀를 진행한다.

 

※주의 - 큰 색종이를 먼저 사용하는 것이 최선이 아닌 이유

위와 같은 경우 큰 색종이부터 사용하게 되면 4x4(초록색)이 먼저 차지하게 되는데,

나머지 '1'을 채우기 위해서는 1x1(파란색) 색종이만 사용할 수 있다.

하지만 종류별로 최대 사용할 수 있는 색종이는 5개 이므로 불가능하다고 판단하여 '-1' 값을 출력하게 된다.

하지만 큰 색종이를 먼저 사용하지 않더라도 위처럼 색종이를 적절하게 사용한다면(3x3 1개 / 2x2 3개 / 1x1 1개)

가능한 경우가 된다.

 

step 4)
재귀 진행에 따라 최소 색종이 결과가 나오면 answer 변수에 최신화한다.

 

모든 재귀 진행을 마쳤을 때 answer에 아무런 변화가 없다면(=초기값 0xfffff과 일치한다면)
가능한 경우가 없다는 뜻이므로 -1 값을 출력한다.

 

코드는 아래와 같다.

import sys

def check(r, c, length, full):
    for i in range(length):
        full -= sum(papers[r+i][c:c+length])
    if full:
        return False
    else:
        return True

def recursive(one, cnt):
    global answer
    if not one:
        answer = min(answer, cnt)
        return
    if cnt >= answer:
        return
    if not sum(used):
        return
    for r in range(10):
        for c in range(10):
            if papers[r][c]:
                for length in range(5, 0, -1):
                    if used[length] and r+length <= 10 and c+length <= 10:
                        if check(r, c, length, length**2):
                            for i in range(r, r+length):
                                for j in range(c, c+length):
                                    papers[i][j] = 0
                            used[length] -= 1
                            recursive(one - length**2, cnt+1)
                            for i in range(r, r+length):
                                for j in range(c, c+length):
                                    papers[i][j] = 1
                            used[length] += 1
                return

papers = []
used = [0]+[5]*5
answer = 0xfffff
one = 0
for _ in range(10):
    paper = list(map(int, sys.stdin.readline().split()))
    one += sum(paper)
    papers.append(paper)
if not one:
    print(0)
else:
    recursive(one, 0)
    print(-1) if answer == 0xfffff else print(answer)

 

문제를 잘못 읽고 코딩을 했을 땐 놓친 부분이 많아서인지 금방해결하였다.
테스트케이스도 전부 통과하여 정답일줄 알았는데... 20%대에서 오답으로 출력되었다.

 

완전탐색으로 접근했다고 생각했는데 '큰 색종이로 먼저 채우는것이 가장 최선이다.'라고 생각한 것은 완전탐색이 아니라 탐욕 알고리즘이었다.

탐욕 알고리즘을 사용할 경우 가장 조심해야하는 것이 "부분의 최적이 곧 모든 경우의 최적이 아닐 수도 있다."는 것이었는데... 보기 좋게 당했다😂

 

실수한 점 & 부족한 점 😩

1. 색종이 종류마다 5개씩 가지고 있다는 점을 놓쳤다.
2. 가장 큰 색종이(5x5)부터 진행하는 것이 최선이라고 생각했다.
3. 재귀를 제대로 구현하지 못했다.

좀 더 집중해서 풀자ㅏㅏㅏ