Baekjoon-14226-이모티콘
27 Sep 20222차원 배열을 이용해 visited를 표시하는 방법 -> 1622 ms 소요
from collections import deque
S = int(input())
N = 1001
# BFS (DP를 써볼까도 했지만 Time complexity는 거의 동일하다)
queue = deque([[1,0]]) # 화면, 클립보드
visited = [[-1 for _ in range(N)] for _ in range(N)]
visited[1][0] = 0
while queue:
monitor, clipboard = queue.popleft()
children = []
children = [(monitor,monitor)]
if clipboard != 0 and monitor+clipboard < N:
children += [(monitor+clipboard, clipboard)]
if monitor > 0:
children += [(monitor-1, clipboard)]
for m,c in children:
if visited[m][c] == -1:
visited[m][c] = visited[monitor][clipboard] + 1
queue.append((m,c))
print(min([s for s in visited[S] if s != -1]))
Dictionary를 이용해 visited를 표시하는 방법 -> 116 ms 소요 (거의 1/10)
from collections import deque
S = int(input())
N = 1001
# BFS (DP를 써볼까도 했지만 Time complexity는 거의 동일하다)
queue = deque([[1,0]]) # 화면, 클립보드
visited = dict()
visited[(1,0)] = 0
while queue:
monitor, clipboard = queue.popleft()
if monitor == S:
print(visited[(monitor,clipboard)])
exit()
children = []
children = [(monitor,monitor)]
if clipboard != 0 and monitor+clipboard < N:
children += [(monitor+clipboard, clipboard)]
if monitor > 0:
children += [(monitor-1, clipboard)]
for m,c in children:
if (m,c) not in visited.keys():
visited[(m,c)] = visited[(monitor,clipboard)] + 1
queue.append((m,c))