백준 18808번 스티커 붙이기

문제

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

18808번: 스티커 붙이기

풀이

이 문제는 예제 입력 8개 모두 다 잘 통과되었는데도 '시간초과'가 자꾸 떠서 이유를 찾느라 꼬박 이틀을 들여다보았던 문제이다. 코드에 이상이 없는 것 같은데 도대체 무엇이 잘못되었는지 찾느라 아주 고생을 했었다.. ㅜ (갠적으로 코딩하면서 이게 젤 힘듦)

아무튼 힘들게 얻은 성공인 만큼 문제의 원인을 기록하여 다음엔 틀리지 않기 위해 글을 남긴다. (그리고 그 누군가 이 문제를 풀며 '시간초과'가 뜬다면 힌트를 얻으시길 바라며...)

 

시간 초과 무려 7번 ㄷㄷ

코드

import sys
input = sys.stdin.readline

# 90도 회전
def rotate(sticker_size, sticker):
    n, m = sticker_size[0], sticker_size[1]
    new_sticker = [[] for _ in range(m)]
    for i in range(n):
        for j in range(m):
            new_sticker[j].insert(0,sticker[i][j])
    return new_sticker

# 노트북에 스티커 붙이기
def attach(sticker_size, sticker):
    global notebook
    global answer
    n, m = sticker_size[0], sticker_size[1]
    for i in range(N-n+1):
        for j in range(M-m+1):
            flag = 0
            tmp = 0
            notebook_copy = [item[:] for item in notebook]
            for si in range(n):
                for sj in range(m):
                    if (sticker[si][sj] == 1):
                        if (notebook_copy[i+si][j+sj] == 1):
                            flag = 1
                            break                        
                        else:
                            tmp += 1
                            notebook_copy[i+si][j+sj] = 1
                    if (si == n-1 and sj == m-1):
                        answer += tmp
                        notebook = notebook_copy
                        return True
                if (flag == 1):
                    break
    return False

N,M,K = map(int, input().split())
notebook = [[0]*M for _ in range(N)]
answer = 0

for _ in range(K):
    n,m = map(int, input().split())
    sticker_size = [n,m]
    sticker = [list(map(int, input().split())) for _ in range(n)]    
    if (max(sticker_size) > max(N,M)):
            continue
    for _ in range(4):
        if (attach(sticker_size, sticker) == True):
            break
        else:
            sticker = rotate(sticker_size, sticker)
            sticker_size = list(reversed(sticker_size))
print(answer)

 

코드 설명

rotate 함수는 스티커를  시계방향으로 90도 회전시켜주는 함수로, 스티커를 떼어낸 그대로 노트북에 붙이려고 하였을 때 붙일 수 없을 때 스티커를 돌리기 위해 사용된다.

- 제일 먼저 기존의 열의 개수(m)를 행위 개수로 하는 new_sticker를 초기화시켜주었다.

- 이후 이중 for문을 돌면서 new_sticker의 가장 왼쪽 열부터 채워주는 방식으로 코드를 짜보았다.

- 기존 스티커의 행은 회전된 스티커의 열을 구성하기 때문이다. (그리고 가장 '위쪽 행'은 가장 '왼쪽 열'이 됨)

 

 

attach 함수는 노트북에 스티커를 붙이는 함수이다.

- 바깥쪽 for문 두개는 왼쪽, 위 지점부터 노트북을 순회한다.(이때의 (i,j)는 모눈종이의 왼쪽 위 지점(0,0)이 붙는 지점이라 생각하면 된다.)

- 안쪽 for문 두개는 스티커(엄밀히 따지면 스티커가 붙여진 모눈종이)의 각 지점을 순회한다.

- 만약 모눈종이의 위치(sticker[si][sj])에 스티커가 채워져있다면, 이제 노트북 그 위치(notebook[i+si][j+sj])에 다른 스티커가 붙어져있는지 확인한다. 즉, 해당 위치에 현재의 스티커를 붙일 수 있는지 확인한다.

- 만약 다른 스티커가 붙어져있다면, 안쪽 이중 for문을 빠져나온다.

- 만약 스티커가 붙어져있지 않다면, 그 다음 스티커 위치를 또 확인하며, 이 과정을 반복한다.

- 스티커의 모든 지점을 순회했다면 스티커를 붙인다. (이 부분 코드는 notebook = notebook_copy 이 부분이다.)

- 안쪽 이중 for문 돌기 전에 notebook을 복사하여 notebook_copy에 저장하는 이유는, flag에 의해 안쪽 이중 for문을 빠져나오면 기존의 notebook으로 rollback해주기 위함이다.

 

여기서 내 기존 코드가 시간 초과가 발생한 이유를 설명하자면,

이 부분이 원래는 notebook_copy = copy.deepcopy(notebook)이었는데, 여기서 사용한 deepcopy 메서드가 시간 소요가 커서이다. 파이썬을 사용할 때 메서드를 가져다 쓰게되면 사실 주의해야 하는 부분이라고 알고 있었는데, 간과하고 있다가 이렇게 호되게 당하고야 말았다..! 하핫 기억하자 "세상에 공짜는 없다."