[백준 14226 🥇] 이모티콘

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

14226번: 이모티콘

문제

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

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

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

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

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

입력

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

출력

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

문제 풀이

import sys
from collections import deque

s=int(sys.stdin.readline())

# init queue
queue=deque()
# 화면에 표시된 이모티콘 개수, 클립보드에 저장된 이모티콘 개수, 소요 시간
queue.append((1, 0, 0))
# 방문 표시
visited=set((1,0,0))

while queue:
    m, c, t = queue.popleft()
    if m==s:
        print(t)
        break
    # 1) 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장
    if m>0 and (m, m, t+1) not in visited:
        queue.append((m, m, t+1))
        visited.add((m, m, t+1))
    # 2) 클립보드에 있는 이모티콘을 화면에 붙여넣기
    if c>0 and (m+c, c, t+1) not in visited:
        queue.append((m+c, c, t+1))
        visited.add((m+c, c, t+1))
    # 3) 화면에 있는 이모티콘 1개 삭제
    if m>0 and (m-1, c, t+1) not in visited:
        queue.append((m-1,c,t+1))
        visited.add((m-1,c,t+1))

• BFS를 이용하면 간단하게 풀리는 문제였다!
• 처음에 화면에 표시된 이모티콘 1개, 클립보드에 복사된 이모티콘 0개, 시간은 0초로 저장해서 큐에 넣어줬다.
• 그리고 이미 검사한 화면에 표시된 이모티콘, 클립보드에 복사된 이모티콘, 경과 시간을 다시 검사해주지 않기 위해서 visited set에 넣어준다.
• 이제 각 상태에 대해서 1번 연산, 2번 연산, 3번 연산을 차례로 수행해주면서 BFS 탐색을 거치고, 화면에 표시된 이모티콘 개수 m이 s와 동일해지면 경과 시간을 출력하고 while문 탐색을 종료해주면 된다.
  • 1번 연산은 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장하는 경우이므로, 화면에 있는 이모티콘 개수가 곧 클립보드의 개수가 된다. 또, 화면에 있는 이모티콘의 개수가 0개라면 이 연산은 클립보드를 비워주는 연산이 되므로 의미가 없다. 그래서 m이 0개 이상인지 확인하고, 해당 연산이 방문하지 않은 상태인지 확인해서 조건을 만족하면 큐에 넣어주고, 방문처리를 해준다.
  • 2번 연산은 클립보드에 있는 이모티콘을 화면에 붙여넣는 경우이므로, 클립보드에 있는 이모티콘을 화면에 추가해준다. 클립보드에 이모티콘이 존재하지 않다면 붙여넣기가 불가능하므로 c>0인지 확인하고, 해당 연산이 방문하지 않은 상태인지 확인해서 조건을 만족하면 큐에 넣어주고 방문처리를 해준다.
  • 3번 연산은 화면에 있는 이모티콘을 1개 삭제해주는 경우이므로, 화면에 있는 이모티콘 개수를 -1해준다. 만약 화면에 이모티콘이 존재하지 않다면 수행할 수 없으므로 m>0인지 확인하고, 방문 여부를 확인한 후에 조건을 만족하면 큐에 넣어주고 방문 처리를 해준다.