문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.
문제 풀이
동생의 위치를 찾는데 걸리는 시간 (최단 거리 구하는 방법과 동일하기 때문에 bfs를 이용)
최단거리를 찾기 위해 이동한 경로 (bfs 이동 경로)
동생의 위치를 찾는데 걸리는 시간은 앞서 푼 숨바꼭질 (1697번) 문제와 동일하다.
그 문제를 해결한 뒤 이동한 경로만 추가해주면 되는 것이다.
최단거리를 찾기 위해 이동한 경로는 bfs를 구하는 로직에서, 큐에 다음 경로를 넣을 때 마다 다음 경로는 현재 위치에서 왔다 라는 경로를 어레이에 따로 저장한다.
bfs를 이용하여 최단 경로를 발견 하였다면, 종료 지점에서 시작 지점이 나올때 까지 경로 어레이에서 정보를 꺼내어 저장하면 된다.
아래 코드에서 경로를 확인할 때 재귀함수를 사용하였는데, stack을 사용하여 경로를 찾는 것도 좋은 방법일 것 같다.
두 가지 코드 모두 확인해보자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class baekjoon13913_2 {
private static int start;
private static int end;
private static boolean[] visit;
private static int[] routeInfo;
private static int[] distInfo;
private static int max = 100_000;
private static ArrayList<Integer> routeResult;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
visit = new boolean[max * 2 + 1];
routeInfo = new int[max * 2 + 1];
distInfo = new int[max * 2 + 1];
bfs13913();
sb.append(distInfo[end] + "\n");
routeResult = new ArrayList<>();
findRoute13913(end);
System.out.println(sb);
}
private static void findRoute13913(int position) {
routeResult.add(position);
if (position == start) {
Collections.reverse(routeResult);
for (int i : routeResult) {
sb.append(i + " ");
}
return;
}
int beforePosition = routeInfo[position];
findRoute13913(beforePosition);
}
private static void bfs13913() {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visit[start] = true;
while (!queue.isEmpty()) {
int currentPosition = queue.remove();
if (currentPosition == end) {
return;
}
int nextPosition = currentPosition + 1;
if (nextPosition < max && !visit[nextPosition]) {
queue.add(nextPosition);
visit[nextPosition] = true;
distInfo[nextPosition] = distInfo[currentPosition] + 1;
routeInfo[nextPosition] = currentPosition;
}
nextPosition = currentPosition - 1;
if (nextPosition >= 0 && !visit[nextPosition]) {
queue.add(nextPosition);
visit[nextPosition] = true;
distInfo[nextPosition] = distInfo[currentPosition] + 1;
routeInfo[nextPosition] = currentPosition;
}
nextPosition = currentPosition * 2;
if (nextPosition <= max * 2 && !visit[nextPosition]) {
queue.add(nextPosition);
visit[nextPosition] = true;
distInfo[nextPosition] = distInfo[currentPosition] + 1;
routeInfo[nextPosition] = currentPosition;
}
}
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// 수빈이와 동생의 숨바꼭질 (동생을 찾아라)
// 수빈이는 +1, -1, *2 로 이동을 할 수 있다.
// 수빈이가 동생을 찾는데 걸리는 최소시간과, 최단경로를 나타내라
// 4, 5, 6, 7 경로로 이동하였을 때
// 최단 경로를 구하는 방법
// dist[5] = 4
// dist[6] = 5
// dist[7] = 6
// dist[4] = 0
// stack에 넣어주고 stack에서 하나씩 프린트를 해주자
// 최단 시간을 구하는 방법
// bfs를 이용해서 구하자
int max = 1000000;
int[] time = new int[max];
int[] dist = new int[max];
boolean[] visit = new boolean[max];
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
visit[x] = true;
Queue<Integer> q = new LinkedList<>();
q.add(x);
while (!q.isEmpty()) {
int n = q.remove();
if (n == y) {
break;
}
// n+1 로 이동했을 때
if (n + 1 < max && visit[n + 1] == false) {
visit[n + 1] = true;
time[n + 1] = time[n] + 1;
dist[n + 1] = n;
q.add(n + 1);
}
if (n - 1 >= 0 && visit[n - 1] == false) {
visit[n - 1] = true;
time[n - 1] = time[n] + 1;
dist[n - 1] = n;
q.add(n - 1);
}
if (2 * n < max && visit[2 * n] == false) {
visit[2 * n] = true;
time[2 * n] = time[n] + 1;
dist[2 * n] = n;
q.add(2 * n);
}
}
Stack<Integer> stack = new Stack<>();
stack.add(y);
int tempY = y;
while (tempY != x) {
tempY = dist[tempY];
stack.add(tempY);
}
System.out.println(time[y]);
while (!stack.isEmpty()) {
int temp = stack.pop();
System.out.print(temp + " ");
}
System.out.println();
}
}