[백준 17136번] 색종이 붙이기

17136번: 색종이 붙이기

area = [list(map(int,input().split())) for _ in range(10)]

size_count = [0]*5

min_value = float("inf")

def check(x,y,n): # n 크기의 색종이를 붙일 수 있는 확인하는 함수

    if (x + n - 1) >= 10 or (y + n - 1) >= 10:
        return False
    
    for i in range(n+1):
        for j in range(n+1):
            if area[x+i][y+j] == 0:
                return False
    return True

def cover(x,y,n):
    for i in range(n+1):
        for j in range(n+1):
            area[x+i][y+j] = 0

def remove(x,y,n):
    for i in range(n+1):
        for j in range(n+1):
            area[x+i][y+j] = 1
        

def dfs(x,y,count):
    global min_value

    if x >= 10:
        min_value = min(min_value,count)

    elif y >= 10:
        dfs(x+1,0,count)

    elif area[x][y] == 1:
        for i in range(5):
            if size_count[i] == 5:
                continue
            if x+i >= 10 or y + i >= 10:
                continue

            if check(x,y,i):
                cover(x,y,i)
                size_count[i] += 1
                dfs(x,y+i+1,count+1)
                size_count[i] -= 1
                remove(x,y,i)
    else:
        dfs(x,y+1,count)

dfs(0,0,0)

if min_value == float("inf"):
    print(-1)
else:  
    print(min_value)

이번 문제는 1x1 부터 5x5 크기의 색종이가 5개씩 존재한다고 할 때, 1이 적힌 칸을 모두 덮는데 필요한 색종이의 최소 개수를 구하는 문제이다.

 

이 문제를 보자마자 그리디로는 풀리지 않고, 완전탐색과 백트래킹으로 풀어야겠다는 생각은 했었는데 2차원 리스트에서 탐색하면서 완전탐색 + 백트래킹을 하는 것이 익숙치 않아서 많은 시간을 잡아먹히게 되었다.

 

먼저 dfs함수에서 각 (x,y) 좌표에서 차지할 수 있는 크기(1x1 ~ 5x5)의 색종이로 덮을 수 있는지 여부를 체크(check)하고, 덮을 수 있다면 색종이로 덮어 0으로 처리(cover)한 뒤 해당 크기의 색종이 사용 개수(size_count)를 +1 해주었다.

 

그 후 다음 경우의 수를 위해서 다시 덮었던 색종이를 제거(remove) 해주는 방식으로 완전탐색과 백트래킹을 사용하였다.

 

다만 여기서 가장 중요한 것은 현재 경로를 방문한 이후에 다음으로 탐색하는 좌표는 x축이나 y축 방향으로 +1 해주어야 한다는 것이고, 만약에 해당 행이나 열이 마지막 인덱스인 경우에는 다음 열이나 행으로 이동해야 한다는 것이다. ⭐️

 

또한, 해당 색종이를 사용한 개수가 5 이상인 경우나 색종이가 범위를 벗어나는 경우에는 continue 해주었다.

 

이번 문제를 통해 완전탐색과 백트래킹에 약하다는 것을 깨달았다. 더 연습해야지  .. 🥲