숨바꼭질 3
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
접근방법
Dijkstra 알고리즘을 다시 복기하려고 풀어보려 한 문제였지만
그냥 BFS로 푸는방법이 가장먼저 떠올라 BFS로 해결했다
하지만 순간이동보다 걸음을 먼저 큐에 넣어버리면
1에서 4로 갈때
1 -> 2 -> 4 로 이동하는데
1 -> 2 를 순간이동이 아닌 걸음으로 이동하게 되어 0시간이 아닌 1시간으로 출력이 된다
따라서 순간이동부터 큐에 넣어주어야 한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 13548 / 숨바꼭질 3
# https://www.acmicpc.net/problem/13549
from collections import deque
def BFS():
q = deque()
q.append(N)
v = [-1] * 100001
v[N] = 0
while q:
cx = q.popleft()
if cx == K:
return v[cx]
for idx in range(2, -1, -1):
if idx < 2:
nx = cx + m[idx]
if 0 <= nx < 100001 and v[nx] == -1:
q.append(nx)
v[nx] = v[cx] + 1
else:
nx = cx * 2
if 0 <= nx < 100001 and v[nx] == -1:
q.append(nx)
v[nx] = v[cx]
N, K = map(int, input().split())
m = [1, -1, 2]
print(BFS())