[BJ] 1697 - 숨바꼭질 (BFS 1차원)

자 수빈이와 동생은 0 <= 100,000에 위치에 있고 동생에 위치를 찾아야한다.

수빈이는 앞과 뒤 로 이동할수있고 현재위치 * 2 의 위치로 이동할수있다.

 

이걸 생각해보면 배열이고 이동거리를 저장해야하니 BFS로 풀 수 있겠다 라는 생각이 들것이다.

 

일단 배열을 모두 -1로 초기화해주고 수빈이의 초기위치를 0으로 만든다 그리고 Queue에 집어넣는다

배열을 모두 -1로 초기화 했으니 수빈이의 거리가 -1이 아니라 양수로 바뀔떄까지 반복을 돌리면 되겠다.

 

그림으로 한번 거리를 봐보자.

 

.

5번은 수빈이의 초기 위치고 17번은 동생의 위치이다.

5 -> 10 -> 9 -> 18 -> 17 로 간다면 4초가 걸리게 될것이다.