[BOJ]13549 - 숨바꼭질 3 (Python)

문제 

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

코드 

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


MAX = 100001
N, K = map(int, input().split())
visit_time = [-1] * MAX
visit_time[N] = 0

queue = deque()
queue.append(N)
while queue:
    x = queue.popleft()
    if x == K:  # 해당 수에 도착
        print(visit_time[x])
        break
    if 0 <= x - 1 < MAX and visit_time[x - 1] == -1:
        visit_time[x - 1] = visit_time[x] + 1
        queue.append(x - 1)
    if 0 <= x * 2 < MAX and visit_time[x * 2] == -1:
        visit_time[x * 2] = visit_time[x]
        queue.appendleft(x * 2)      # 비용이 0인 경우를 가장 우선시하기 위해서 큐의 맨 앞으로 보냄
    if 0 <= x + 1 < MAX and visit_time[x + 1] == -1:
        visit_time[x + 1] = visit_time[x] + 1
        queue.append(x + 1)

 

풀이 

앞서 풀었던 숨바꼭질 문제와 비슷하지만 시간의 개념이 들어간다. 

백준의 질문 글들을 보면 다익스트라로 푸는 방식도 있다고 했지만 아직 자세히 배우지 않아서 나는 그냥 BFS로 풀었다. 

이 문제에서 주의해야할 점은 2가지이다. 

 

• 시작했을 때의 시간이 0초이기 때문에 나머지 시간들은 -1로 초기화 한 뒤에 문제를 푼다 
  • 모든 원소를 0으로 초기화했을 때는 N = 1, K = 2인 경우에 0이 나오지 않고 1이 나오게 된다
• x * 2의 경우, 우선 순위가 다른 것들보다 높기 때문에 deque에 넣을 때 맨 앞에 넣어준다 → appendleft()

다음에 다익스트라로도 풀어봐야지...😊