문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.
이 문제는 기존 숨바꼭질 문제에서 스택을 이용하여 답을 출력하는 문제이다.
그리고 int[ ] parent 배열을 추가하여 이전 위치를 저장해야 한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
/*
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.
*/
public class Test13913 {
static int n, m;
static boolean[] visit;
static int[] parent;
static Queue<Position> Q;
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());
m = Integer.parseInt(st.nextToken());
// 방문체크를 위한 배열
visit = new boolean[100001];
// 이전 위치를 기억하기 위한 배열
parent = new int[100001];
Q = new LinkedList<>();
Q.offer(new Position(n, 0));
// bfs시작
bfs();
}
static void bfs() {
while (!Q.isEmpty()) {
// 큐의 사이즈만큼 for문을 돌린다. 그 이유는 시간마다 로직을 나누기 위함이다.
// ex) 만약 time = 2 일때 큐에 4개의 값이 있다면 4개을 돌리고 시간을 증가시킨다.
// 여기선 따로 시간도 담는 클래스를 넣어서 필요없어보이지만
// 이렇게 관리를 하는게 여러모로 편하다.
int size = Q.size();
for (int t = 0; t < size; t++) {
Position tmp = Q.poll();
// 만약 목표 숫자에 도달했다면 parent[]을 따라서 이전 값들을 스택에 저장한다.
if (tmp.x == m){
System.out.println(tmp.time);
Stack<Integer> stack = new Stack<>();
stack.push(tmp.x);
int num = tmp.x;
// 스택에 숫자들을 parent[] 배열을 타고가면서 저장한다.
while (true){
if (num == n) break;
stack.push( parent[num]);
num = parent[num];
}
// 저장을 다 했다면 스택에서 꺼내 출력한다.
while (!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
return;
}
// -1, +1, *2 값들을 계산한다.
int n1 = tmp.x - 1;
int n2 = tmp.x + 1;
int n3 = tmp.x * 2;
// 움직일 값이 방문하지 않았고 정상범위 안 이라면 큐에 넣고
// 방문체크와 parent[] 배열에 지금 값을 저장한다.
// 여기서는 단 하나의 값만 출력하면 되기 때문에 여기서 "visit[n1] = true;" 을 하지만
// 만약 전체 가능 방법수를 구하거나 할때는 중복도 허용이 되기때문에 "Position tmp = Q.poll();"
// 다음 줄에 visit[tmp.x] 를 넣어주면 된다.
if (n1 >= 0 && !visit[n1]){
Q.offer(new Position(n1, tmp.time+1));
parent[n1] = tmp.x;
visit[n1] = true;
}
// 움직일 값이 방문하지 않았고 정상범위 안 이라면 큐에 넣고
// 방문체크와 parent[] 배열에 지금 값을 저장한다.
if (n2 <= 100000 && !visit[n2]){
Q.offer(new Position(n2, tmp.time+1));
parent[n2] = tmp.x;
visit[n2] = true;
}
// 움직일 값이 방문하지 않았고 정상범위 안 이라면 큐에 넣고
// 방문체크와 parent[] 배열에 지금 값을 저장한다.
if (n3 <= 100000 && !visit[n3]){
Q.offer(new Position(n3, tmp.time+1));
parent[n3] = tmp.x;
visit[n3] = true;
}
}
}
}
// 값과 시간을 저장하는 클래스
static class Position {
int x, time;
public Position(int x, int time) {
this.x = x;
this.time = time;
}
}
}
더 더 더!