[백준]17136 색종이붙이기

1. 풀이

(1) 1이나오는 지점에서 가능한 색종이를 종류별(1~5)로 모두 붙여본다

(2) 크기가 현재 ans보다 크면 백트래킹

​

2. 소스코드

(1) 두번의 DEEPCOPY, 시간초과

안전한 코드를 위해 stack이 시작할때 리스트들을 copy해주었다.

하지만 스택에 넣을 때 copy를 해준 후 넣기 때문에 L에는 영향이 없다. 따라서 스택이 시작할 때 다시 copy를 해주지 않아도 된다.

from collections import deque
from copy import deepcopy
L=[]
for i in range(10):
    L.append(list(map(int,input().split())))

stack=deque([[[0 for i in range(5)],L,0]])

ans=26

def isAllZero(L):
    for i in L:
        if sum(i)!=0:
            return False
    return True

while(stack):
    temp=stack.pop()
    used=list(temp[0])          #시간초과 유발부분!
    copiedL=deepcopy(temp[1])   #시간초과 유발부분!
    sumAns=sum(used)
    '''
    print("--------------")
    print(used)
    print(num)
    for i in copiedL:
        print(i)
    print("--------------")
    '''

    if sumAns>=ans:
        continue


    #모두0이면 통과
    if isAllZero(copiedL):
        if sumAns<ans:
            ans=sumAns
        continue
    else:
        for i in range(10):
            for j in range(10):
                #해당지점 찾음
                isFind=False
                if copiedL[i][j]==1:
                    isFind=True
                    # 1*1 ~ 5*5
                    for k in range(1,6):
                        if used[k-1]<5 and i+k-1<10 and j+k-1<10:
                            isPossible=True
                            for l in range(k):
                                for m in range(k):
                                    if copiedL[i+l][j+m]==0:
                                        isPossible=False
                                        break
                                if not isPossible:
                                    break
                            if isPossible:
                                tempUsed = list(used)
                                tempL = deepcopy(copiedL)
                                tempUsed[k-1]+=1
                                for l in range(k):
                                    for m in range(k):
                                        tempL[i+l][j+m]=0
                                '''
                                print("처리결과")
                                for z in tempL:
                                    print(z)
                                print(tempUsed,num+1)
                                '''
                                stack.append([tempUsed,tempL])
                    break
            if isFind:
                break




if ans==26:
    print(-1)
else:
    print(ans)

 

(2) 통과

from collections import deque
from copy import deepcopy
L=[]
for i in range(10):
    L.append(list(map(int,input().split())))

stack=deque([[[0 for i in range(5)],L,0]])

ans=26

def isAllZero(L):
    for i in L:
        if sum(i)!=0:
            return False
    return True

while(stack):
    temp=stack.pop()
    used=temp[0]
    copiedL=temp[1]
    sumAns=sum(used)
    '''
    print("--------------")
    print(used)
    print(num)
    for i in copiedL:
        print(i)
    print("--------------")
    '''

    if sumAns>=ans:
        continue


    #모두0이면 통과
    if isAllZero(copiedL):
        if sumAns<ans:
            ans=sumAns
        continue
    else:
        for i in range(10):
            for j in range(10):
                #해당지점 찾음
                isFind=False
                if copiedL[i][j]==1:
                    isFind=True
                    # 1*1 ~ 5*5
                    for k in range(1,6):
                        if used[k-1]<5 and i+k-1<10 and j+k-1<10:
                            isPossible=True
                            for l in range(k):
                                for m in range(k):
                                    if copiedL[i+l][j+m]==0:
                                        isPossible=False
                                        break
                                if not isPossible:
                                    break
                            if isPossible:
                                tempUsed = list(used)
                                tempL = deepcopy(copiedL)
                                tempUsed[k-1]+=1
                                for l in range(k):
                                    for m in range(k):
                                        tempL[i+l][j+m]=0
                                '''
                                print("처리결과")
                                for z in tempL:
                                    print(z)
                                print(tempUsed,num+1)
                                '''
                                stack.append([tempUsed,tempL])
                    break
            if isFind:
                break




if ans==26:
    print(-1)
else:
    print(ans)