【白俊】【Python】14226番表情パック

💡詰まった部分
bfsに近いけど塞がれてる...!この問題で注意しなければならないのは二つのことだ.現在の画面に表示される表情の数と、クリップボードに格納されている表情の数です.どうすればいいのか分からず、検索で解決しました.問題を起こす人は本当に天才だ.
💡解答方法
簡単に二次元配列で解決すればいいだけです.1行目には現在の画面に表示されている表情の個数、2行目にはクリップボードに記憶されている表情の個数が格納されます.たとえばgraph[3][2]=5の場合、現在の画面に表示されている表情記号の数は3であり、クリップボードに格納されている表情記号の数は2である.この場合の最短値は5です.
この場合,画面に任意の数の表情が存在しても,クリップボードに格納されている表情は異なるため,最小値を求める過程を経なければ答えが得られない.
📝ソースコード

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

S = int(input())
graph = [[-1]*(S+1) for _ in range(S+1)]
queue = deque()

def bfs():
    queue.append([1, 0])
    graph[1][0] = 0
    while queue:
    	# s는 screen, c는 clipboard
        s, c = queue.popleft()
        # 클립보드에 현재 화면에 있는 이모티콘을 복사
        if graph[s][s]==-1:
            graph[s][s] = graph[s][c]+1
            queue.append([s, s])
        # 클립보드에 있는 이모티콘을 화면에 붙여넣기
        if s+c<=S and graph[s+c][c]==-1:
            graph[s+c][c] = graph[s][c]+1
            queue.append([s+c, c])
        # 현재 화면에 있는 이모티콘 한 개 제거
        if s-1>0 and graph[s-1][c]==-1:
            graph[s-1][c] = graph[s][c]+1
            queue.append([s-1, c])
bfs()
# 최솟값을 구하는 과정
temp = graph[S][1]
for i in range(1, S+1):
    temp = min(temp, graph[S][i])
print(temp)