[Python] 13549: 숨바꼭질 3

https://www.acmicpc.net/problem/13549
알고리즘 분류 : BFS

문제:
수빈이 위치 : N , 동생의 위치 : K (0 ≤ N, K ≤ 100,000)
수빈이가
걷기 - 1초 소요, x+1 혹은 x-1 로 이동
or
순간이동 - 0초 소요, 2*x 로 이동
을 해서 동생을 찾을 수 있는 가장 빠른 시간을 출력하라.

풀이:

from collections import deque

N, K = map(int, input().split())
q = deque() # 빈 리스트를 초기화하여 빈 deque 객체 생성. 
q.append(N)

# visited 배열 : -1이면 방문하지 않은 곳, 아니면 그 곳까지 가는데 걸린 시간
visited = [-1 for _ in range(100001)] # visited 리스트를 -1의 100001개 요소로 초기화. (0부터니까)
visited[N] = 0 # 수빈이의 출발 위치니까 방문하는데 걸리는 시간은 0임.

while q: # 큐가 빌 때까지 반복.
    x = q.popleft() # 큐처럼 구현한 거라, 가장 앞의 요소를 꺼내 x에 저장
    if x == K: # 동생이 있는 위치에 다다르면 걸린 시간을 print 함
        print(visited[x])
        break # break를 통해 while 문 탈출
    if 0 <= x-1 < 100001 and visited[x-1] == -1:
        visited[x-1] = visited[x] + 1
        q.append(x-1)
    if 0 < x*2 < 100001 and visited[x*2] == -1: # 0을 포함하면 계속 0이 반복됨. 그래서 빼 줘야함
        visited[x*2] = visited[x]
        q.appendleft(x*2)  # 2*s 가 다른 연산보다 더 높은 우선순위를 가지기 위해 큐의 가장 앞에 넣어줌
    if 0 <= x+1 < 100001 and visited[x+1] == -1:
        visited[x+1] = visited[x] + 1
        q.append(x+1)
        
# 2*s가 소요시간 0이기 때문에 다른 연산보다 더 높은 우선순위를 가져야 하고, 
# 그래서 큐의 앞에 넣어줬으므로 같은 위치에 여러번 방문해서 값을 갱신할 필요가 없음.

• pop(0)과 popleft()의 차이
  : pop(0)을 하면 리스트의 크기에 따라 O(n)의 시간이 걸리는 반면, popleft()를 하면 리스트의 맨 마지막 값을 가져오는 pop()과 마찬가지로 O(1)의 시간이 걸린다.