[ 17136 ] [ DFS ] 색종이 붙이기

 

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

17136번: 색종이 붙이기

---

풀이 과정

---

1. 가능한 모든 경우의 수에 대해서 탐색한다.(dfs 사용)
   1. 배열을 왼쪽 위에서부터 오른쪽 아래로 진행하면서 1을 만나게 되면, 해당 위치에서 1x1부터 5x5까지 붙일수 있는지 검사하고, 붙일수 있다면 붙인 후 다음 1을 찾는다. 이 때, 붙이게 된 경우 1을 0으로 수정해 주고, 다시 떼는 경우 0을 1로 수정해 준다. 
   2. 붙일수 있는지 없는지는 현재 위치[i, j]에서 [i~i+색종이 크기] [j~j+색종이 크기] 정사각형에 0이 있는지 없는지로 판단한다.
   3. 색종이의 개수가 1x1, 2x2, 3x3, 4x4, 5x5 모두 5장씩만 있으니 개수를 따로 저장 관리해주어야 한다.
   4. 모두 붙인 경우 최소 색종이 개수를 갱신시켜 준다.
2. recursion에서 하나의 위치만 담당해야 하는데, 가지치기가 제대로 되지 않아 계속 틀렸다.,, 하나의 recursion에서 하나의 색종이만 담당하도록 색종이를 발견하면 다음 recursion은 색종이 다음 위치부터 시작하게 처리하였으며, 색종이 처리가 끝나면 바로 리턴하도록 수정하였더니 통과하였다.

 

---

소스 코드

---

import sys

input = lambda : sys.stdin.readline().rstrip()

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

card_count = [0, 5, 5, 5, 5, 5] # 각 색종이 개수

min_card_count = int(10e9)

def check_card(x, y, size):
    if x+size > len(matrix) or y+size > len(matrix[0]):
        return False
    
    for i in range(x, x+size):
        for j in range(y, y+size):
            if matrix[i][j] == 0:
                return False
    return True

def set_value_to_matrix(x, y, size, value):
    if x+size > len(matrix) or y+size > len(matrix[0]):
        return
    for i in range(x, x+size):
        for j in range(y, y+size):
            matrix[i][j] = value

def check_finish():
    p = sum([p for m in matrix for p in m if p == 1])
    if p > 0:
        return False
    else:
        return True

def get_card_count():
    total_card_count = 0
    for i in range(1, 6):
        total_card_count += (5 - card_count[i])
    return total_card_count

def dfs(a, b):
    global min_card_count
    for i in range(a, len(matrix)):
        for j in range(b, len(matrix[0])):
            if matrix[i][j] == 1:
                for card in range(1, 6):
                    if not check_card(i, j, card):
                        return   
                    if card_count[card] > 0:
                        card_count[card] -= 1
                        set_value_to_matrix(i, j, card, 0)
                        dfs(i, 0)
                        set_value_to_matrix(i, j, card, 1)
                        card_count[card] += 1
                return
                        
    if check_finish():
        min_card_count = min(min_card_count, get_card_count())

dfs(0, 0)
if min_card_count == int(10e9):
    print(-1)
else:
    print(min_card_count)