문제

---

이해

---

0 ~ 100,000 위치에 수빈이와 동생이 위치해있다.

수빈이가 동생을 찾으려고 한다.

수빈이는 1초 동안 걷거나 순간이동할 수 있다.

걷는 경우 한 칸을 이동하기 때문에 현위치에서 +1, -1로 이동한다.

순간이동은 현 위칭서 x2의 위치에 이동한다.

수빈이가 동생을 찾는 가장 빠른 시간과 해당 방법으로는 몇 가지가 있는지 구해라.

접근

---

동생 위치에 도달할 수 있는 시간을 구해야 한다.

또한, 수빈이는 +1, -1, x2의 위치로 이동할 수 있기 때문에 BFS를 써야하는 것으로 보인다.

하지만 가장 빠른 시간으로 찾는 방법이 총 몇가지인지 구해야 하기 때문에 동생 위치에 도달한다 하더라도 BFS를 종료하면 안된다.

내가 세운 아이디어는 다음과 같다.

1. 수빈이는 BFS를 통해 동생 위치에 최단 시간으로 도착.
2. BFS의 큐에는 해당 시간에 도달할 수 있는 경우들이 포함되어 있음.
3. BFS를 최단 시간과 동일한 큐의 원소까지만 추가적으로 탐색.
4. 추가 탐색에서 동생 위치에 도달하면 카운트 +1

코드

---

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int K;
	static int min = Integer.MAX_VALUE;
	static int min_cnt = 0;
	static int[] min_d;

	static class cdnt {
		int pos;
		int depth;

		public cdnt(int pos, int depth) {
			this.pos = pos;
			this.depth = depth;
		}
	}

	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());

		min_d = new int[100001];
		Arrays.fill(min_d, Integer.MAX_VALUE);
		BFS(N);

		System.out.println(min);
		System.out.println(min_cnt);
	}

	static void BFS(int start) {
		Queue<cdnt> q = new LinkedList<>();
		q.add(new cdnt(start, 0));

		while (!q.isEmpty()) {
			cdnt now = q.poll();

			if (now.pos == K) {
				if (min < now.depth) {
					continue;
				} else if (min > now.depth) {
					min = now.depth;
					min_cnt = 1;
				} else {
					min_cnt++;
				}
				continue;
			}

			cdnt[] next = new cdnt[3];
			next[0] = new cdnt(now.pos + 1, now.depth + 1);
			next[1] = new cdnt(now.pos - 1, now.depth + 1);
			next[2] = new cdnt(now.pos * 2, now.depth + 1);

			for (cdnt next_cdnt : next) {
				if (isOutBound(next_cdnt) || min_d[next_cdnt.pos] < next_cdnt.depth) {
					continue;
				}

				min_d[next_cdnt.pos] = next_cdnt.depth;
				q.add(next_cdnt);
			}
		}
	}

	static boolean isOutBound(cdnt c) {
		return c.pos < 0 || c.pos > 100000;
	}
}

일반적인 BFS 수행과 같지만 끝처리만 유의해서 작성하자.

결과

---