[Python] 백준 / gold / 17136 : 색종이 붙이기 (자세한 주석 포함)

문제 링크 : https://www.acmicpc.net/problem/17136

백트래킹 문제. 구현하기도 까다로웠고, 시간초과를 해결하느라 힘들었다.
예전에 [1655 : 가운데를 말해요] 문제를 해결하다가 백준에 질문을 올렸을 때 답변주신 lambda 님.. 그 답변이 이 문제를 푸는데도 핵심이 됐습니다..
질문 했던 글 : https://www.acmicpc.net/board/view/81833

python 에서는 리스트와 같은 reference type 데이터를 다룰 때 깊은 복사와 얕은 복사를 잘 고려해야된다.

첫 시도 때 시간초과가 났던 이유 : 매 백트래킹 과정에서, 남아있는 색종이 현황 paper 리스트, 남아있는 커버해줘야 할 종이들 need_cover 셋을 복사 (deep copy) 했기 때문. copy.deepcopy 는 생각보다 시간을 많이 잡아먹는 메서드다. need_cover 를 set 으로 사용해서, 앞으로 덮어줘야 할 좌표 값들을 모두 담고 복사해서 다음 dfs 에 넘겨줬었는데, 그럴 필요없이 int 값으로 남은 좌표 수만 저장했더니 시간 초과를 면했다.

풀이과정

• 색종이를 모두 사용했을 경우 ( sum(paper) == 0 인 경우 ) 가지치기.

• 덮어야 할 좌표들을 모두 덮은 경우 ( need_cover == 0 인 경우 ) 가지치기.

• 색종이를 처음부터 끝까지 모두 탐색했을 경우 가지치기.

• (핵심) 현재까지 구해진 answer 보다 작은 값을 도출해낼 가능성이 없다고 판단할 경우 가지치기. 예를들어, 현재 answer == 5 인데, 현재 뻗어나가려는 가지가 무조건 5 를 넘는 값을 도출할 것이 뻔하다면 가지를 친다. 이렇게 해야 시간초과를 피할 수 있다.

• 색종이 커버는 5x5, 4x4, 3x3 ... 순서로 모두 덮어보기. 이게 시간 효율이 좋다.

• 그리디적으로 풀면 반례가 있어서 오답처리 된다. 백트래킹으로 모두 고려해줘야 한다. 반례는 백준 예제 입력 7번.

파이썬 코드 (정답 코드)

import sys
import copy
graph = []
answer = 9999

for _ in range(10):
    graph.append(list(map(int, sys.stdin.readline().split())))


# 현재 좌표, 남은 종이들, 덮어야할 좌표 집합
def dfs(x, y, paper, need_cover):
    global answer

    # 색종이를 모두 사용했을 경우
    if sum(paper) == 0:
        # 덮어야 할 곳이 없는 경우
        if need_cover == 0:
            answer = min(answer, 0)
            return
        # 덮어야 할 곳이 남은 경우
        else:
            return

    # 덮어야 할 곳을 모두 덮은 경우
    if need_cover == 0:
        answer = min(answer, 25 - sum(paper))
        return

    # 색종이의 끝까지 탐색했을 경우
    if x == 10:
        # 덮어야 할 곳을 모두 덮은 경우
        if need_cover == 0:
            answer = min(answer, 25 - sum(paper))
            return
        # 다 못 덮은 경우
        else:
            return

    # (핵심) 현재 answer 보다 값이 작아질 가능성이 없으면 가지치기
    if 25 - sum(paper) > answer:
        return

    # 현재 좌표가 덮을 필요가 없는 좌표 (= 0) 인 경우
    if graph[x][y] == 0:
        # 다음 행으로 넘어가야 할 경우
        if y == 9:
            dfs(x+1, 0, paper, need_cover)
        # 다음 열로 넘어가야 할 경우
        else:
            dfs(x, y+1, paper, need_cover)

    # 현재 좌표가 덮어야 할 좌표 (= 1) 인 경우
    elif graph[x][y] == 1:
        # 색종이가 남아는 있지만, 갖고 있는 색종이로는 더 이상 커버를 할 수 없는 형태인 경우를 거르기 위해서.
        can_cover_more = False

        # 1x1, 2x2, ... 5x5 색종이로 덮을 수 있는지 완전탐색.
        for size in reversed(range(1, 6)):
            # 사용하고 싶은 색종이 사이즈가 남아있지 않으면 패스
            if paper[size] == 0:
                continue
            # 이 사이즈 색종이로 커버가 가능할지
            can_cover_with_this_size = True
            # 이 사이즈에서 커버하게 될 좌표들
            have_to_cover = []
            for a in range(size):
                for b in range(size):
                    # 색종이 밖으로 나가거나 0 을 발견하면 False
                    if (not (0 <= x+a < 10 and 0 <= y+b < 10)) or graph[x+a][y+b] == 0:
                        can_cover_with_this_size = False
                        break
                    else:
                        have_to_cover.append((x+a, y+b))

            # 이 사이즈 색종이로 커버가 가능하다면.
            if can_cover_with_this_size:
                # 커버 가능한 색종이를 찾았으므로 True
                can_cover_more = True
                new_paper = copy.deepcopy(paper)
                new_need_cover = need_cover - len(have_to_cover)
                # 커버해야 할 좌표들을 0 으로 커버해준다.
                for cover_x, cover_y in have_to_cover:
                    graph[cover_x][cover_y] = 0
                # 사용한 색종이 제거
                new_paper[size] -= 1

                # 다음 좌표로 dfs 탐색
                if y + size == 10:
                    dfs(x+1, 0, new_paper, new_need_cover)
                else:
                    dfs(x, y+size, new_paper, new_need_cover)

                # 백트래킹 해서 돌아왔으면 다시 1로 돌려줌
                for cover_x, cover_y in have_to_cover:
                    graph[cover_x][cover_y] = 1

        # 커버 할 수 있는 색종이가 없을 때
        if not can_cover_more:
            return


# 커버해야할 좌표들 구하기
need_cover_num = 0
for i in range(10):
    for j in range(10):
        if graph[i][j] == 1:
            need_cover_num += 1

# (0, 0) 에서 부터 dfs 시작.
dfs(0, 0, [0, 5, 5, 5, 5, 5], need_cover_num)

if answer == 9999:
    print(-1)
else:
    print(answer)