[백준] 13549번(숨바꼭질 3)

백준 13549번

최종 제출 코드

from collections import deque

n, k = map(int,input().split())
queue = deque()
visited = [-1 for _ in range(100001)]

def bfs():

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

    if visited[k] != -1:
      return visited[k]
      
    value = queue.popleft()

    if value*2 <= 100000 and visited[value*2] == -1:
      visited[value*2] = visited[value]
      queue.appendleft(value*2)
      
    if value-1 >= 0:
      if visited[value-1] == -1:
        visited[value-1] = visited[value]+1
        queue.append(value-1)
      
    if value+1 <= 100000:
      if visited[value+1] == -1:
        visited[value+1] = visited[value]+1
        queue.append(value+1)

print(bfs())

◼ deque 자료구조의 특징 활용

• deque은 양쪽에서 원소를 넣고, 빼고 할 수 있음
• x2 연산의 경우 0초가 걸림
  ⇒ 더하기, 빼기 연산을 통해 산출된 원소보다 더 높은 우선순위를 가져야 함
  ex) 5에서 -1, +1, x2 각각 4, 6, 10의 값이 나올 수 있는데 10은 물론이고 10의 배수인 20, 20의 배수인 40 ... 이런식으로 x2을 통해 나오는 값들은 이전 값들과 같은 연산시간을 가져야 하기 때문에, 맨 앞에 원소를 넣어서 먼저 처리해준다.