[백준] 13549번: 숨바꼭질 3

📌 알고리즘 정리

---

📃 문제

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

13549번: 숨바꼭질 3

---

✍ 풀이과정

import sys
from collections import deque
MAX = 100001

n, k = map(int, input().split())
queue = deque([n])
dist = [-1]*MAX
dist[n] = 0

while queue:
    i = queue.popleft()

    if i == k:
       print(dist[i])
       break

    if i*2 < MAX and dist[i*2] == -1:
        queue.appendleft(i*2)
        dist[i*2] = dist[i]
    if i-1>=0 and dist[i-1] == -1:
        queue.append(i-1)
        dist[i-1] = dist[i] + 1
    if i+1< MAX and dist[i+1] == -1:
        queue.append(i + 1)
        dist[i+1] = dist[i] + 1

옛날에 풀어본 문제였고 bfs로 풀었다.

 

(문제 A->B)에서는 +"1"과 *2밖에 없어서 뒤로 돌아오지 못하는 반면에

이 문제는 -1도 있기 때문에 dist를 두어 해당 위치에 방문했는지를 확인해야 한다.

* (3 -> 4 -> 3) 같은 경우를 방지하기 위해서

 

(*2)를 하는 경우에는 초가 증가하지 않으므로 appendleft를 해주었다.