간단하게 BFS로 풀 수 있는 문제라고 생각합니다.
하지만 다른 풀이로 데이크스트라로 문제를 풀어보도록 해보겠습니다.
가장 맨 처음에 있는 위치 N을 기준으로 -1, +1 로 가는 경우의 가중치는 1입니다.
두배로 가는 경우의 가중치는 0입니다.
이것을 기분으로 문제를 풀어봅시다.
(N,0)을 우선순위 큐에 넣습니다.
이제 (N-1, 1), (N+1, 1), (2 * N, 0)을 큐에 넣습니다.
다만 다익스트라이기 때문에 거리가 갱신된 경우만 큐에 넣습니다!
그렇게 해서 모든 노드들간의 최소 거리를 구했다면 이제 K 노드로 가는 최소 거리를 구해주면 문제를 해결합니다.
다익스트라 문제를 풀기 위해서는 거리 배열, 우선순위 큐가 필요합니다!
각 노드에 대한 거리를 기록하기 위하여 배열을 최댓값으로 초기화하여 선언합니다.
dist = new int[100_001];
Arrays.fill(dist, 100_000);
// 시작점의 거리는 0
dist[N] = 0;
이제 우선순위큐를 선언하고 거기에 N을 넣어줍니다.
PriorityQueue<Node13549> pq = new PriorityQueue<>();
pq.add(new Node13549(N, 0));
이제 3가지 경우(+1, -1, *2)에 대해서 가장 최소로 가는 길을 탐색합니다.
while(!pq.isEmpty()) {
Node13549 cur = pq.poll();
if(dist[cur.idx] < cur.dist)
continue;
if(cur.idx - 1 >= 0 && dist[cur.idx-1] > cur.dist + 1) {
dist[cur.idx - 1] = cur.dist + 1;
pq.add(new Node13549(cur.idx-1, cur.dist + 1));
}
if(cur.idx + 1 <= 100_000 && dist[cur.idx + 1] > cur.dist + 1) {
dist[cur.idx + 1] = cur.dist + 1;
pq.add(new Node13549(cur.idx+1, cur.dist + 1));
}
if(cur.idx * 2 <= 100_000 && dist[cur.idx * 2] > cur.dist) {
dist[cur.idx * 2] = cur.dist;
pq.add(new Node13549(cur.idx*2, cur.dist));
}
}
이를 통해 우리는 원하는 답인 dist[K]를 구할 수 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class No13549 {
static int N, K;
static int[] dist;
public static void main(String[] args) throws IOException {
input();
pro();
}
private static void pro() {
dijkstra();
System.out.println(dist[K]);
}
private static void dijkstra() {
dist = new int[100_001];
Arrays.fill(dist, 100_000);
dist[N] = 0;
PriorityQueue<Node13549> pq = new PriorityQueue<>();
pq.add(new Node13549(N, 0));
while(!pq.isEmpty()) {
Node13549 cur = pq.poll();
if(dist[cur.idx] < cur.dist)
continue;
if(cur.idx - 1 >= 0 && dist[cur.idx-1] > cur.dist + 1) {
dist[cur.idx - 1] = cur.dist + 1;
pq.add(new Node13549(cur.idx-1, cur.dist + 1));
}
if(cur.idx + 1 <= 100_000 && dist[cur.idx + 1] > cur.dist + 1) {
dist[cur.idx + 1] = cur.dist + 1;
pq.add(new Node13549(cur.idx+1, cur.dist + 1));
}
if(cur.idx * 2 <= 100_000 && dist[cur.idx * 2] > cur.dist) {
dist[cur.idx * 2] = cur.dist;
pq.add(new Node13549(cur.idx*2, cur.dist));
}
}
}
private static void input() 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());
br.close();
}
}
class Node13549 implements Comparable<Node13549> {
int idx;
int dist;
public Node13549(int idx, int dist) {
this.idx = idx;
this.dist = dist;
}
@Override
public int compareTo(Node13549 o) {
return this.dist - o.dist;
}
}