백준 13549. 숨바꼭질3 (with. Python)

백준 13549. 숨바꼭질

아으 나 멍청이 아닐까 진짜

🎈 문제 요약

n 위치에서 k 위치로 이동하는 최소 시간 구하기.

이동은 다음과 같이 할 수 있다.
0초 (순간이동) : (현위치)*2
1초 : (현위치)+1 또는 (현위치)-1

🎈 풀이

BFS 알고리즘을 사용해야한다는 것은 알아서 초기 문제 접근은 아주아주 쉽게 했다.
다만 너무 쉽게 생각해서 처음에는 아무 생각없이 냅다 deque에 때려박아버리고 메모리 초과 @!
암튼 방문처리는 꼭꼭 해주자 !-! 그리고 계속 틀린 것으로 나와서 뭐지.. 했는데

젤 중요했던 거!!! 순서!!!!
순간이동을 할 때는 시간이 0초로 시간 추가가 되지 않는다. 그러므로 BFS 과정에서 가장 먼저 판단되괴 deque로 넣어주어야 하고, 시간도 그대로이므로 appendleft()로 deque 가장 앞 쪽에 넣어주어야 한다.

(이걸 몰랐네 ~~)

🎈 코드

from collections import deque

# 입력값
n, k = map(int, input().split())

# 방문처리 & 거리 테이블
visited = [0]*100001

# 테이블 초기화
visited[n] = 1

queue = deque()
queue.append([n, 0])

# BFS
while queue:
  x, t = queue.popleft()

  while x==k:
    print(t)
    break

  if 2*x<=100000 and not visited[2*x]:
    queue.appendleft([2*x, t])
    visited[2*x] = 1

  if x+1<=100000 and not visited[x+1]:
    queue.append([x+1, t+1])
    visited[x+1] = 1

  if 0<=x-1 and not visited[x-1]:
    queue.append([x-1, t+1])
    visited[x-1] = 1

늘긴 늘었지만 갈 길은 멀다 ^~^