[백준/자바] 1697 숨바꼭질

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

5 17

예제 출력 1

4

---

설명

해당 문제는 다음과 같은 알고리즘 분류에 해당하는 문제다.

• 그래프 이론

• 그래프 탐색

• 너비 우선 탐색 

수빈이의 위치가 X일 때 X-1, X+1, 2*X의 위치로 이동할 수 있다.

방문 여부를 표시하는 visited와 해당 위치까지 이르는 시간을 표시하는 num변수를 설정한다.

이때, 수빈과 동생 모두 100000까지 거리를 이동할 수 있으므로 배열의 범위는 100001까지 지정한다.

위치 이동시 무조건 1초씩 이동하기 때문에 num++한다.

코드