수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
아.. 이런것도 BFS로 풀 수 있구나 싶었다 처음에는 ㅋㅋㅋ
처음에 DP인줄알고.. ㅋㅋㅋ 사고력을 넓히는? 계기가 되었다!
내일 CJ올리브네트웍스 코딩테스트가 있다! 잘 준비하자
package Sample;
import java.util.*;
public class Main {
static int[] map = new int[200001];
static boolean[] visited = new boolean[200001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
Queue<Integer> q = new LinkedList<>();
if(N > 0) {
for(int i = N; i < map.length; i *= 2)
{
visited[i] = true;
q.add(i);
}
}
else {
visited[0] = true;
q.add(0);
}
if(visited[K])
{
System.out.print(map[K]);
return ;
}
while(!q.isEmpty()) {
int now = q.poll();
// System.out.print(now + " ");
if(now == K)
{
q.clear();
System.out.print(map[now]);
return ;
}
if(now < map.length - 1 && !visited[now + 1])
{
q.add(now + 1);
map[now + 1] = map[now] + 1;
for(int i = now + 1; i < map.length; i *= 2)
{
if(!visited[i])
{
visited[i] = true;
q.add(i);
map[i] = map[now + 1];
}
}
}
if(now > 0 && !visited[now - 1])
{
q.add(now - 1);
map[now - 1] = map[now] + 1;
visited[now - 1] = true;
if(now > 1) {
for(int i = now - 1; i < map.length; i *= 2)
{
if(!visited[i])
{
visited[i] = true;
q.add(i);
map[i] = map[now - 1];
}
}
}
}
}
}
}