[백준] 17136번 색종이 붙이기 - 파이썬/백트래킹

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

1차 풀이

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

cnt = 0
cnt5 = 0
cnt4 = 0
cnt3 = 0
cnt2 = 0

def check(x,y,n):

    for i in range(x,x+n):
        for j in range(y,y+n):
            if graph[i][j] == 0:
                return False
    return True

def trans(x,y,n):

    for i in range(x,x+n):
        for j in range(y,y+n):
            graph[i][j] = 0


for i in range(6):
    for j in range(6):
        if check(i,j,5):
            trans(i,j,5)
            cnt+=1
            cnt5+=1


for i in range(7):
    for j in range(7):
        if check(i,j,4):
            trans(i,j,4)
            cnt+=1
            cnt4 += 1

for i in range(8):
    for j in range(8):
        if check(i,j,3):
            trans(i,j,3)
            cnt+=1
            cnt3 += 1

for i in range(9):
    for j in range(9):
        if check(i,j,2):
            trans(i,j,2)
            cnt+=1
            cnt2 += 1

print(graph)

remain = sum(map(sum,graph))
print(cnt5,cnt4,cnt3,cnt2)

if remain > 5 or cnt5 > 5 or cnt4 >5 or cnt3 >5 or cnt2>5:
    print(-1)
else:
    cnt += remain
    print(cnt)

5칸 색종이부터 1칸 색종이까지 대보면서 갯수를 구하는 식으로 풀었다.

예제는 다 통과했는데 제출하면 실패했다.

반례는 아래와 같았다.

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0

이러한 배열은 3x3 1칸, 2x2 3칸, 1x1 3칸으로 표현할 수 있는 배열이다.

그러나 큰 색종이부터 변환해가면 4x4 1칸, 1x1 8칸으로 각각 5개인 색종이로 나타낼 수 없는 배열이 된다.

2차풀이

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

min_ans = 9999999

nums = [5,4,3,2]
array = []

def check(x,y,n,graph):

    for i in range(x,x+n):
        for j in range(y,y+n):
            if graph[i][j] ==0:
                return False
    return True

def trans(x,y,n,graph):
    for i in range(x,x+n):
        for j in range(y,y+n):
            graph[i][j] = 0

def dfs(depth):
    global min_ans
    if depth == 4:
        graph_copy = [arr[:] for arr in graph]
        temt_list = []
        for elem in array:
            temt = 0
            for i in range(11-elem):
                for j in range(11-elem):
                    if check(i,j,elem,graph_copy):
                        trans(i,j,elem,graph_copy)
                        temt+=1
            if temt > 5:
                return
            temt_list.append(temt)

        remain = sum(map(sum, graph_copy))
        if remain > 5:
            return
        else:
            temt_list.append(remain)

        check_ans = sum(temt_list)

        if check_ans < min_ans:
            min_ans = check_ans

        return

    for i in range(4):
        if nums[i] not in array:
            array.append(nums[i])
            dfs(depth+1)
            array.pop()

dfs(0)

if min_ans == 9999999:
    print(-1)
else:
    print(min_ans)

순서를 5->4->3->2 가 아니고 뒤죽박죽으로 했다.

1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

그러나 위의 반례에 막혀서 틀렸다.

이 반례를 보고 문제 접근 방식이 완전히 틀렸다는 생각이 들었다. 색종이 하나를 정하고 왼쪽 위부터 탐색했는데, 접근 방식을 바꿔야 할 필요가 있었다.