[백준] 14226번(이모티콘)

백준 14226번

최종 제출 코드

from collections import deque

s = int(input())
queue = deque()
visited = [[-1 for _ in range(1001)] for _ in range(1001)]

def bfs():

  visited[1][0] = 0
  queue.append([1,0])
  
  while queue:

    value, clipboard = queue.popleft()

    if value == s:
      return visited[value][clipboard]

    nodes = [[value, value], [value+clipboard, clipboard], [value-1, clipboard]]

    for i in nodes:
      if i[0] == 0 or i[0] > 1000:
        continue
      if visited[i[0]][i[1]] == -1:
        queue.append(i)
        visited[i[0]][i[1]] = visited[value][clipboard]+1
        
print(bfs())

◼️ bfs를 활용해서 문제풀이

• nodes 리스트에 세가지 연산에 대한 이모티콘의 개수, 클립보드에 복사된 이모티콘의 개수를 저장한다
• nodes 원소의 값이 범위 내인지 & 접근 가능한지 검사하고,
• 접근 가능할 경우 이 전에 거쳤던 연산과 결과인지 확인한다.
• 이전에 방문한 적 없는 (값, 클립보드)이면 visited 값 업데이트
• 값이 S와 같으면 visited[값][클립보드]를 return하고 함수 종료