[백준 3주차 - 13913] 숨바꼭질 4 (Java)

📌 문제

 

📝 풀이과정

1. 가장 빠른 시간

이전에 숨바꼭질 2 문제에서 BFS로 가장빠른 시간을 출력해보았다 (12851번 문제풀이 참고)

 

2. 어떻게 이동해야 하는 지

이동 경로를 추적하는 문제이므로 prev배열으로 구현할 수 있다

prev[next]=now;

 

for(int i=k;i!=n;i=prev[i]){
    trace.add(i);
}
trace.add(n);
Collections.reverse(trace);

 

1) k인 17부터 prev[17], prev[16], prev[8] .... i가 5가 아닐 때까지 ArrayList<Integer> trace에 i를 넣는다

2) 마지막으로 n인 5를 넣어준다

3)  그럼 trace에는 17, 16, 8, 4, 5 순서로 들어있고, Collections.reverse로 뒤집어 주면 된다!

 

💻 코드

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

public class Main{
	static final int MAX=200000;
	static int visited[]=new int[MAX+4];
	static int prev[]=new int[MAX+4];
	static ArrayList<Integer> trace=new ArrayList<>();
	static int n,k;
	static void bfs(int here){
		visited[here]=1;
		Queue<Integer>queue=new LinkedList<>();
		queue.add(here);

		while(!queue.isEmpty()){
			int now=queue.poll();
			for(int next:new int[]{now-1,now+1,now*2}){
				if(next>=0 && next<=MAX){
					if(visited[next]==0){                                                                                              
						visited[next]=visited[now]+1;
						queue.add(next);
						prev[next]=now;
					}
				}
			}
		}
		for(int i=k;i!=n;i=prev[i]){
			trace.add(i);
		}
		trace.add(n);
		Collections.reverse(trace);
	}
    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());
		
		bfs(n);
		
		System.out.println(visited[k]-1);
		for(int item:trace){
			System.out.print(item+" ");
		}
		
	}
}