[Python] 14226 이모티콘

문제

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

풀이과정

• 입력
  보내는 이모티콘 개수 S

• 출력
  이모티콘 S개를 만들기 위해 필요한 시간의 최솟값

• 고려할 것

  최단 시간을 구하는 문제 → BFS 활용

  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.

  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.

  3. 화면에 있는 이모티콘 중 하나를 삭제한다.

     visited((화면 이모티콘 개수, 클립보드 이모티콘 개수))
     -> 불필요한 정보를 최소화 하기위해 딕셔너리 사용

• 주의할 점
  큐의 첫 요소를 할당해야하는데 첫번째의 원소가 2개의 값으로 구성된 튜플 이어야 한다.

    queue = deque() # 화면 이모티콘 개수, 클립보드 이모티콘 개수
    queue.append((1,0))
    screen, clipboard = queue.popleft()

from collections import deque
import sys
input = sys.stdin.readline

S = int(input())
queue = deque() # 화면 이모티콘 개수, 클립보드 이모티콘 개수
queue.append((1,0))

visited = dict()
visited[(1, 0)] = 0

while queue:
    screen, clipboard = queue.popleft()
    # 종료 조건
    if screen == S: # 이모티콘 S개를 만들면 종료
        print(visited[(screen, clipboard)]) # 연산횟수 출력
        break
    # 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
    if (screen, screen) not in visited.keys(): # 방문하지 않았을 때
        visited[(screen, screen)] = visited[(screen, clipboard)] + 1
        queue.append((screen, screen))
    # 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
    if (screen + clipboard, clipboard) not in visited.keys():
        visited[(screen + clipboard, clipboard)] = visited[(screen, clipboard)] + 1
        queue.append((screen + clipboard, clipboard))
    # 화면에 있는 이모티콘 중 하나를 삭제한다.
    if (screen -1, clipboard) not in visited.keys():
        visited[(screen - 1, clipboard)] = visited[(screen, clipboard)] + 1
        queue.append((screen - 1, clipboard))