현재 위치-1, 현재 위치+1, 현재위치*2
현재 위치를 기준으로 이동방식 3가지를 조합하여 BFS를 이용하여 K로까지 걸린 시간을 구한다.
import java.util.*;
import java.io.*;
public class HidePlay {
/* baekjoon 1697 */
// 위치를 담을 수 있는 객체
public static class Location {
int time; // 얼마나 걸렸는지
int position; // 현재 위치
Location(int time, int position) {
this.time = time;
this.position = position;
}
}
static int N;
static int K;
static Queue<Location> queue; // 다음에 방문할 곳 저장
static boolean[] visited; // 방문했는지 확인
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
queue = new LinkedList<>();
visited = new boolean[100001]; // 0<= K <= 100000이므로 1만 더 크게 설정
bfs();
// Runtime.getRuntime().gc();
// long usedMemory = Runtime.getRuntime().totalMemory() -
// Runtime.getRuntime().freeMemory();
// System.out.print(usedMemory + " bytes");
}
public static void bfs() {
queue.add(new Location(0, N)); // 초기위치 Queue에 넣기
visited[N] = true; // 현재 위치 방문했다고 표시
while (!queue.isEmpty()) {
Location current = queue.poll();
// 현재 위치가 K이면 종료
if (current.position == K) {
System.out.println(current.time);
return;
}
// 현재위치-1 로 이동할때
if (0 <= current.position - 1 && !visited[current.position - 1]) {
queue.add(new Location(current.time + 1, current.position - 1));
visited[current.position - 1] = true;
}
// 현재위치+1 로 이동할때
if (current.position + 1 < visited.length && !visited[current.position + 1]) {
queue.add(new Location(current.time + 1, current.position + 1));
visited[current.position + 1] = true;
}
// 현재위치*2 로 이동할때
if (current.position * 2 < visited.length && !visited[current.position * 2]) {
queue.add(new Location(current.time + 1, current.position * 2));
visited[current.position * 2] = true;
}
}
}
}