14226: 이모티콘

• 최소 시간 -> 최단 거리 -> bfs

import sys
from collections import deque

def bfs():
    state = [1, 0, 0] #state[0]: stdout, state[1]: clip board, state[2]: seconds
    queue = deque([]); queue.append(state)

    while queue:
        curr = queue.popleft()

        if curr[0] == S:
            print(curr[2])
            return
        
        if curr[0] >= 0 and curr[1] >= 0:
            if curr[1] != 0:
                one = [curr[0], curr[0], curr[2]+1]; queue.append(one)
                two = [curr[0]+curr[1], curr[1], curr[2]+1]; queue.append(two)
                three = [curr[0]-1, curr[1], curr[2]+1]; queue.append(three)
            else:
                one = [curr[0], curr[0], curr[2]+1]; queue.append(one)
                three = [curr[0]-1, curr[1], curr[2]+1]; queue.append(three)

   
S = int(input())

bfs()

• 처음에 작성한 코드 (메모리 초과 발생)
• state들을 list에 모두 담아놓는 방식에서 메모리가 낭비된듯
  -> visit라는 이름의 dictionary 자료형을 사용
  -> visit[(stdout, clip board)] = seconds 형식으로

import sys
from collections import deque

def bfs():
    queue = deque([]); queue.append((1, 0))

    while queue:
        curr = queue.popleft()

        if curr[0] == S:
            print(visit[curr])
            return
        
        if (curr[0], curr[0]) not in visit:
            queue.append((curr[0], curr[0])); visit[(curr[0], curr[0])] = visit[curr] + 1
        if (curr[0]-1, curr[1]) not in visit:
            queue.append((curr[0]-1, curr[1])); visit[(curr[0]-1, curr[1])] = visit[curr] + 1
        if (curr[0]+curr[1], curr[1]) not in visit:
            queue.append((curr[0]+curr[1], curr[1])); visit[(curr[0]+curr[1], curr[1])] = visit[curr] + 1

   
S = int(input())

visit = dict()
visit[(1, 0)] = 0
bfs()

• visit에 다음으로 append하려는 node가 이미 있다면 어차피 최소 시간이 아닌거니까(제자리로 다시 돌아오는 경우임) 해당 경우를 if (key of next node) not in visit:를 통해 걸러줌