[백준] 1697 숨바꼭질(Python)

백준 - 1697 숨바꼭질

문제

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

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

입력

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

출력

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

예제

---

알고리즘

1. 갈 수 있는 방향
   x - 1 , x + 1 , 2 * x

2. BFS 탐색으로 깊이를 계산하면서 탐색

   깊이: 바로 전 깊이 + 1

3. 의문점
   처음엔 bfs 함수를 아래와 같이 작성했다. k값(도착점)을 만나면 깊이를 출력하고 함수를 끝내는 라인을 for 문 안에 작성하면 더 빨리 찾을 수 있다 생각해서 for문 안에 썼는데 틀렸다. 근데 뭐가 문제인지 아직도 모르겠다,,,,,

for i in (x - 1, x + 1, 2 * x):
	if 0 <= i <= MAX and not depth[i]:
		depth[i] = depth[x] + 1
		q.append(i)
    # 수정하기 전 코드, k를 찾으면 바로 끝내는 코드를 for 문 안에 넣음 -> 틀림, 왜?????????????
    if i == k:
		print(depth[i])
		break

---

코드

from collections import deque

MAX = 100000

def bfs(n, k):
	q = deque()
	q.append(n)
	while q:
		x = q.popleft()
		if x == k:
			print(depth[x])
			break
		for i in (x - 1, x + 1, 2 * x):
			if 0 <= i <= MAX and not depth[i]:
				depth[i] = depth[x] + 1
				q.append(i)

n, k = map(int, input().split())
depth = [0] * (MAX + 1)
bfs(n, k)