문제

코드

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

queue = deque()
n,k = map(int,input().split())

def bfs():
    queue.append(n)
    while(queue):
        soobin = queue.popleft() #수빈이 위치 저장 
        if(soobin==k):
            print(sec[soobin])
            break
        for walk in (soobin-1,soobin+1,soobin*2):
            if (0<=walk<MAX and  sec[walk]==0 ):
                sec[walk] = sec[soobin]+1
                queue.append(walk)
                #5는 어쩔수 없이 한번 오게된당.. 
        

MAX = 100001
sec = [0] * MAX #초 리스트 
bfs()

해설

이전까지는 DFS로 풀었는데 이번 같은 경우 너비우선탐색이 아닌 깊이 우선 탐색으로 한다면 무한히 들어가서 끝이 나지 않을것이다.
왜냐하면 수빈이가 동생 자리에 오는 경우 멈추게 했는데 잘못된 길로 쭈우욱 들어가면 절대로 수빈이가 동생자리로 올 수 없기 때문이다.

그렇기에 이번 문제는 BFS로 풀어야한다.
우선, 풀기전에 그래프를 한번 그려봤다

삐뚤한거 죄송합니당..돌리면 사진이 잘리더라구여ㅣ,,,
기본 메모장에선 못돌리길래 힝...
쨌든
수빈이가 5에 있을때 17까지 가는 방법은
그래프에서 봤듯이
5 -> 4 -> 8 -> 16 -> 17
5 -> 10 -> 9 -> 18 -> 17
두가지 방법이 있는데
힌트에서는 아래를 줬다
뭐,, 위나 아래나 같은 시간이 나오니 상관없긴하다...

그렇기에 BFS를 이렇게 짜줬다.

BFS 풀이

def bfs():
    queue.append(n)
    while(queue):
        soobin = queue.popleft() #수빈이 위치 저장 
        if(soobin==k):
            print(sec[soobin])
            break
        for walk in (soobin-1,soobin+1,soobin*2):
            if (0<=walk<MAX and  sec[walk]==0 ):
                sec[walk] = sec[soobin]+1
                queue.append(walk)
                #5는 어쩔수 없이 한번 오게된당.. 

수빈이의 제일 첫 거리를 큐에 넣어주고 그 거리를 for 문을 써서 돌아준다.
그렇게 3가지 케이스를 모두 돌아주고 그 케이스들을 sec이라는 리스트에 넣어줌으로써 그 거리까지 가는데 시간을 저장하는 sec라는 리스트가 있다.
이렇게 for문이 queue에 3가지 케이스를 넣어주고 다음 케이스를 시작하면서 뒤에 붙여주는 형식으로 이어나간다.
그런데, 만약 팝한 수빈이 위치가 동생과 같은 위치라면 그 위치까지 가기 위한 시간을 출력하면서 break해주면 된다.

즉, 5가 제일 먼저 큐에 들어오고 그 이후로

이런식으로 쭉쭉 너비우선적으로 탐색을 진행한다는것이다.

음..!

DFS만 써서 이때까지 다 잘풀려서 BFS는 알필요 없넹~ 했는데
BFS도 중요할때가있다..!
둘다 익숙해지자!!!
앞에 DFS로 푼 문제들도 BFS로 고민해봐야겠다.

for step in (k-1,k+1,k*2)

이 for문은 자주 사용하지 않아서 익숙하지 않았어서 까먹고 있었는데
다시 알아두고 가자 !
k-1 -> k+1 -> k*2 순으로 step에 들어간다 !