[Java] 백준 13913번 : 숨바꼭질 4

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력 1

5 17

예제 출력 1

4
5 10 9 18 17

예제 입력 2

5 17

예제 출력 2

4
5 4 8 16 17

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, K, T;
	private static int[] time, parent;
	private static int dx[] = { -1, 1 };

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		time = new int[100001];
		parent = new int[100001];

		bfs();	// 수빈이가 동생을 찾는 가장 빠른 시간 탐색
		System.out.println(time[K]);
		int now=K;
		Stack<Integer> stack=new Stack<>();
		while(now!=N) {	// 수빈이가 동생을 찾는 경로를 뒤에서부터 거꾸로 탐색하며 스택에 넣어줌
			stack.add(now);
			now=parent[now];
		}
		stack.add(now);
		while(!stack.isEmpty()) {	// 스택에 있는 값을 하나씩 꺼내주면, 그 순서가 수빈이가 동생을 찾은 경로가 됨
			int get=stack.pop();
			System.out.print(get+" ");
		}
	}

	private static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(N);
		time[N]=0;

		while (!queue.isEmpty()) {
			int q = queue.poll();
			if (q == K) return;

			int nx;
			for (int i = 0; i < 3; i++) {
				if (i == 2)
					nx = q * 2;
				else
					nx = q + dx[i];

				if (nx >= 0 && nx <= 100000 && time[nx]==0 ) {
					time[nx]=time[q]+1;	// nx번 점에 도착한 시간 저장
					parent[nx]=q;	// nx번 점에 도착하기 전에 들른 점 저장
					queue.add(nx);
				}
			}
		}
	}
}

처음에는 리스트에 경로를 저장해주어 수빈이가 동생을 찾은 경우에 해당 리스트의 값들을 순서대로 출력해주려고 하였으나 시간 초과가 발생하였습니다. 그래서 다음으로 생각한 방법은 각 점을 방문할 때마다 방문한 시간과 이전에 방문한 점을 저장하는 것이었습니다. 그리고 도착점에서부터 거꾸로 경로를 탐색하며 수빈이에 도달할때까지의 경로 정보를 스택에 넣어주었습니다. 그 다음 스택의 값들을 하나씩 꺼내면 수빈이가 동생을 찾는 경로를 구할 수 있습니다.