문제풀이
Queue를 사용해 bfs를 구현했다.
단순히 동생에게 가는 최소 시간을 구하는게 아니라 최소 시간과 가는 방법까지 포함한다.
따라서 Queue에 push할때 visit을 체크하지 않고 Queue에서 poll할때 visit을 체크한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int limit = 100000;
boolean[] visit = new boolean[limit + 1];
Queue<Integer> q = new LinkedList<>();
q.add(N);
visit[N] = true;
if(N == K) {
System.out.println(0);
System.out.println(1);
return;
}
int second = 0;
int count = 0;
while(!q.isEmpty()) {
int size = q.size();
for(int s = 0; s < size; s++) {
int temp = q.poll();
visit[temp] = true;
if(temp - 1 == K) {
count++;
} else if(temp - 1 >= 0 && !visit[temp - 1]) {
q.add(temp - 1);
}
if(temp + 1 == K) {
count++;
} else if(temp + 1 <= limit && !visit[temp + 1]) {
q.add(temp + 1);
}
if(temp * 2 == K) {
count++;
} else if(temp * 2 <= limit && !visit[temp * 2]) {
q.add(temp * 2);
}
}
second++;
if (count != 0) {
break;
}
}
System.out.println(second);
System.out.println(count);
}
}