BFS: 백준 13549 숨바꼭질 3

문제: https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

풀이:

1697번 문제 숨바꼭질 1에서 순간이동을 하는 경우엔 1의 가중치가 없어지도록 한 문제이다.

x+1, x-1, x*2 로 이동하는 경우를 각각 처리해주어야 한다. 만약 순간이동할 경우 큐의 맨 앞에 순간이동한 후의

좌표를 추가 해주어 연산에 우선순위를 주어야 한다.

이렇게 하면 각 좌표로 이동하는 최단시간이 dist 배열에 저장된다.

  

정답:

import sys
from collections import deque
input = sys.stdin.readline()

MAX = 100001
visited = [False] * MAX
dist = [-1]*MAX

n, k = map(int, input.split())
queue = deque()
queue.append(n)
visited[n] = True
dist[n] = 0

while queue:
    x = queue.popleft()
    if x*2 < MAX and visited[x*2] == False:     # 순간이동
        queue.appendleft(x*2)       # 순간이동 할 경우 큐 맨 앞에 추가
        visited[x*2] = True
        dist[x*2] = dist[x]
    if x+1 < MAX and visited[x+1] == False:     # x+1 이동
        queue.append(x+1)           # 이동한 값은 뒤에 추가
        visited[x+1] = True
        dist[x+1] = dist[x] + 1
    if x-1 >= 0 and visited[x-1] == False:      # x-1 이동
        queue.append(x-1)           # 이동한 값은 뒤에 추가
        visited[x-1] = True
        dist[x-1] = dist[x] + 1

print(dist[k])

# 순간이동을 할 경우 appendleft() 함수를 사용해 queue에서 먼저 탐색되도록 한다.
# 다른 연산보다 더 높은 우선순위를 가지기 위함.