수테크📱⌚️👀

문제 😵‍💫

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

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

입력!

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

출력!

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

내 풀🦷

# 1697. 숨바꼭질
from collections import deque
def bfs(start, depth):
    visited = [0] * 100001
    q = deque()
    q.append((start, depth))
    visited[start] = 1
    while q:
        s, d = q.popleft()

        if s == K:
            return d

        for nxt_s in [s-1, s+1, s*2]:
            if 0 <= nxt_s <= 100000 and (not visited[nxt_s] or visited[nxt_s] > d+1):
                q.append((nxt_s, d+1))
                visited[nxt_s] = d+1

N, K = map(int, input().split())
visited = [0] * K
result = dfs(N, 0)
print(result)

 처음에 도대체가 어떻게 접근해야할지도 모르겠고 dp나 while문으로 풀어야겠다 싶었는데 알고보니 bfs 문제였다ㅜㅜ

시작점과 깊이를 넣어서 시작점이 끝점과 같아지면 return으로 깊이를 받아주면 최소값을 구할 수 있다!!

어려웠던 부분은 방문 했던 곳 또는 깊이가 더 깊은곳과 그전까지의 깊이에 해당하는 값이 같았을때는 배제해 주어야 한다는 것이었다... 다른 분들 코드를 보았을때는 이미 방문한곳을 continue로 넘겨서 간단히 해결해 주는것을 볼 수 있었다...어떻게 풀어야할지까지 고민한 문제는 오랜만이라 더욱 힘들었다 😂😂😂😂