숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력1

5 17

예제 출력1

4

문제 풀이

• BFS로 풀어야한다는 생각은 있었으나 어떤 식으로 풀어야할지 몰라 그냥 BFS 코드의 기본 구조를 따라서 코딩했다.

from collections import deque
n,m=map(int,input().split())
vec=[1,-1,2]
queue=deque([(n+1,1),(n-1,1),(n*2,1)])

while queue:
    loc,sec=queue.popleft()
    if loc==m:
        break
    for v in vec:
        if v!=2:
            queue.append((loc+v,sec+1))
        else:
            queue.append((loc*2,sec+1))
print(sec)

• 수빈이가 움직이는 방법은 +1,-1,*2이기 때문에 초마다 그 거리를 모두 계산해서 BFS 형식으로 풀려고 했다.
• 하지만 그렇게하면 queue에 너무 많이 값이 들어가버려서 메모리 초과 가 발생했다.
• 이걸 해결하려고 고군분투하다가 만약 동생이 있는 자리보다 멀리 나간상태에서 *2를 하면 아무 소용이 없기 때문에 if문으로 그것을 막아주려고 했다.

from collections import deque
n,m=map(int,input().split())
vec=[1,-1,2]
queue=deque([(n,0)])

while queue:
    loc,sec=queue.popleft()
    if loc==m:
        print(sec)
        break
    for v in vec:
        if v!=2:
            if 0<loc+v<=m:
                queue.append((loc+v,sec+1))
        else:
            if 0<loc*v<=m:
                queue.append((loc*2,sec+1))

• 하지만 이렇게 해도 조건문이 부족해서 queue에 너무 많이 넣게 되는건지 메모리초과가 발생했다.
• 결국 다른 사람의 풀이를 참고하면서 코드를 짜려고 했다. 근데 내가 생각한 방식이랑 너무 비슷한데 시간초과, 메모리초과 때문에 코드를 수정해야하니까 억울한 기분...
• 이러나저러나 내가 아직은 다양한 방법을 찾지 못했고 실력이 부족하기 때문이라고 생각하면서 풀이를 보고 공부했다.

from collections import deque
n,m=map(int,input().split())
queue=deque([n])
visited=[0]*100001

while queue:
    loc=queue.popleft()
    if loc==m:
        print(visited[loc])
        break
    for v in [loc+1,loc-1,loc*2]:
        if 0<=v<=100000 and not visited[v]:
            visited[v]=visited[loc]+1
            queue.append(v)

• 100000을 max로 정해준 이유는 문제에서 제한입력 수가 100000이기 때문이다.
• 저 숫자를 고려하지 못해서 조건문을 제대로 짜지 못했던게 아쉽다.