[백준 17136번] 색종이 붙이기(파이썬)

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

17136번: 색종이 붙이기

전형적인 백트레킹 문제입니다.

이 문제는 모든 종이를 다 돌면서

종이를 크기에 따라 다 붙어야하기 때문에

종이의 모든 칸을 다 봐야합니다.

그래서 이 문제는

탐색과 백트래킹

두 가지를 해주면 되는 문제입니다.

탐색형 백트레킹은 처음이어서

이 문제를 처음 풀었을 때

많이 당황하기도 했었네요.

#백준 17136번

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

def check(x,y):
    if x<0 or x>=10 or y<0 or y>=10:
        return False
    return True

answer=26
def dfs(x,y,cnt):
    global answer
    if x>=10:

        answer=min(answer,cnt)
        return

    if y>=10:
        dfs(x+1,0,cnt)
        return
    if room[x][y]==1:
        for k in range(5):
            if paper[k]>=5:
                continue

            if x+k<0 or x+k>=10 or y+k<0 or y+k>=10:
                continue
            ok=True
            for cx in  range(x,x+k+1):
                for cy in range(y,y+k+1):
                    if room[cx][cy]==0:
                        ok=False
                        break
                if not ok:
                    break
            if ok:
                for cx in range(x, x + k+1):
                    for cy in range(y, y + k+1):
                        room[cx][cy]=0

                paper[k]+=1
                dfs(x,y+k+1,cnt+1)
                paper[k]-=1
                for cx in range(x, x + k+1):
                    for cy in range(y, y + k+1):
                        room[cx][cy] = 1

    else:
        dfs(x,y+1,cnt)

dfs(0,0,0)
if answer==26:
    answer=-1
print(answer)

저는 y를 움직이면서 탐색하는 방식을 선택했습니다.

 

 

이 문제에서 주의할 점은

멈출 지점을 구하는 건데요.

저는 종이를 더 못넣는 경우에

함수가 끝나는 걸로 되어있습니다.

만약에 1을 5개 넘은 상태에서

지금 1밖에 넣을 수 밖에 없는 상태라면

더 이상 종이를 넣어도 모든 1을 다 덮을 수 없기 때문에

-1을 출력해야합니다.

 

 

백트레킹에 대한 이해를 증진시킬 수 있는 좋은 문제입니다.

문제를 정리하면서

탐색+백트래킹

두 가지를 모두 공부하면 좋을 것 같습니다.