[백준14226번] 이모티콘 / Python3

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

4

예제 출력 2

4

예제 입력 3

6

예제 출력 3

5

예제 입력 4

18

예제 출력 4

8

나의 풀이

해당 문제는 BFS를 사용해 3 가지 연산을 모두 확인해주면 된다. 처음에 아무 생각없이 1초마다 3가지의 연산을 모두 큐에 담았었다. 역시나 메모리 초과가 발생하였다. 이를 해결하기 위해서는 visited를 사용해서 해당 화면의 이모티콘 수와 클립보드의 이모티콘 수가 방문이 되었었는지를 따져주어야 한다. 그리고 또 주의해야할 점은 각 연산에도 특별한 조건이 필요하다. 이 조건은 아래에서 설명하겠다.

우선 방문 여부를 저장하기 위하여 visited배열을 만들어야한다. 필자는 visited[화면의 이모티콘 수][클립보드의 이모티콘 수]를 방문 여부를 저장하는 형식으로 정하였다. 이렇게 해주면 어떠한 다른 연산들을 거쳐 똑같은 경우가 나온다면 통합하여 하나의 경우로 따져주어 중복을 없애줄 수 있다. 따라서 visited를 [s+1][s+1]의 크기로 만들어주어 방문여부를 저장해주었다.

1번 연산은 화면의 이모티콘을 클립보드에 저장하는 연산으로 방문 여부를 확인해주는 것 말고는 따로 확인해주어야할 조건이 없다. 반면 2번 연산의 경우를 보자. 앞에서 visited를 [s+1][s+1]의 크기만큼 선언을 해주었다. 그렇기때문에 화면의 이모티콘과 클립보드의 이모티콘이 합쳐진 수가 s를 넘는 경우가 발생하면 visited에서 인덱스 에러가 발생하게 된다. 따라서 display + clip <= s라는 조건이 필요하다. 마찬가지로 3번의 연산에서도 화면의 이모티콘들을 1씩 감소를 시키다보면 0보다 작아질 수 있기때문에 display - 1 >= 0이라는 조건이 필요하다.

코드

# 14226번 이모티콘
from collections import deque

# bfs
def bfs(s):
    q = deque()
    q.append([1,0,0])

    visited = [[False for _ in range(s+1)] for _ in range(s+1)]
    visited[1][0] = True

    while q:
        display, clip, cnt = q.popleft()

        if display == s:
            return cnt

        # 1번 연산 - 현재 이모티콘 클립보드에 저장
        if not visited[display][display]:
            visited[display][display] = True
            q.append([display, display, cnt+1])

        # 2번 연산 - 화면에 클립보드를 복사
        if display+clip <= s:
            if not visited[display+clip][clip]:
                visited[display+clip][clip] = True
                q.append([display+clip, clip, cnt+1])

        # 3번 연산 - 화면에서 하나 삭제
        if display - 1 >= 0:
            if not visited[display-1][clip]:
                visited[display-1][clip] = True
                q.append([display-1, clip, cnt+1])

# main
s = int(input())
print(bfs(s))