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

문제: https://www.acmicpc.net/problem/13913

 

 

조건

• TimeLimit = 2s
• 수빈이 위치(0<=N<=10만), 동생 위치(0<=K<=10만)
• 수빈이가 1초마다 이동한다 -> 걷기 = x+=1, 순간이동 = 2x (x = 현재위치)
• 수빈이가 동생을 찾는 가장 빠른 시간과, 그때의 이동 순서를 출력하라

 

풀이

• 최단시간이므로 BFS를 사용하자
  • N이 10만으로 크지만, 1차원 배열이므로 완전탐색이 가능하다
  • 이동 순서는 매번 배열을 들고다닐 필요가 없고, 직전에 어디서 왔는지만 기억하면 된다
  • 따라서 이동순서는 int[]로 기억해두자

 

코드

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


public class Main {

	static StringBuilder sb;
	static StringTokenizer st;
	static int n;
	static int k;
	static boolean[] visited;
	static int minTime = Integer.MAX_VALUE;
	static int[] befores;
	
	
	
	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
				
		visited = new boolean[100_001];
		befores = new int[100_001];
		
		// bfs
		bfs();
		
		// result
		sb = new StringBuilder();
		sb.append(minTime).append("\n");
		
		ArrayList<Integer> result = new ArrayList<>();
		result.add(k);
		
		int b = befores[k];
		while (b != n) {	
			result.add(b);
			b = befores[b];
		}
		if (k != n) result.add(n);
		Collections.reverse(result);
		
		for(int x : result) sb.append(x).append(" ");
		System.out.print(sb);
		
	}
	
	
	
	static void bfs() {
		
		Deque<Node> q = new ArrayDeque<>();
		q.add(new Node(n, 0, n));
		visited[n] = true;
		
		while (!q.isEmpty()) {
			
			Node cur = q.pop();
			befores[cur.x] = cur.before;
			
			// 갱신
			if (cur.x == k) {
				minTime = cur.t;
				break;
			}
			
			// 탐색
				
			int x1 = cur.x + 1;
			int x2 = cur.x - 1;
			int x3 = 2*cur.x;
			int[] xArr = {x1, x2, x3};
			
			for (int nx : xArr) {
				
				if (!(0<=nx && nx<=100_000)) continue;
				if (visited[nx]) continue;
				
				visited[nx] = true;
				q.add(new Node(nx, cur.t+1, cur.x));
			}
		}	
	}
	
	
	
	static class Node {
		
		int x;
		int t;
		int before;
		
		Node(int x, int t, int before) {
			this.x = x;
			this.t = t;
			this.before = before;
		}
		
	}
	
	
	
}