(Python/🥇2)백준알고리즘 17136번 : 색종이 붙이기

 

문제 바로가기 

문제:

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

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다. 종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력:

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

출력:

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

 

풀이:

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

graph = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(10)]
# 5장씩
possible = [5, 5, 5, 5, 5]
result = 26

def checkXY(y, ny, x, nx):
    for i in range(y, ny + 1):
        for j in range(x, nx + 1):
            if graph[i][j] == 0:
                return False
    return True


def attach(y, ny, x, nx, param):
    for i in range(y, ny + 1):
        for j in range(x, nx + 1):
            graph[i][j] = param


def bt(count):
    global result
    for y in range(10):
        for x in range(10):
            if graph[y][x]:
                for i in range(5):
                    ny, nx = y + i, x + i
                    # 범위 안이면서, 색종이가 남음
                    if possible[i] != 0 and ny < 10 and nx < 10:
                        # 방향 다 가능한지 체크
                        if checkXY(y, ny, x, nx):
                            attach(y, ny, x, nx, 0)
                            possible[i] -= 1
                            bt(count + 1)
                            attach(y, ny, x, nx, 1)
                            possible[i] += 1
                return
    result = min(result, count)


bt(0)
print(result if result != 26 else -1)

 

 

풀이: 

 

1. 일단 색종이 별로 5장씩만 들고 있다 .

2. 색종이로 덮을때 0 인 부분이 없어야 한다 .

를 생각해서

 

x, y좌표를 쭈욱 돌면서 1을 만나면 덮어준다.

덮기전에 체크를 해야하는건 색종이 크기만큼 모든 공간이 1로 가득차야 한다는 것이다.

 

그게 가능하다면 bt로 다음것을 불러준다.

 

return 으로 더이상 탐색 할 필요가 없으니 제껴준다.