[JAVA] 백준 13549 - 숨바꼭질 3

 

 

🤔 문제 접근

+1, -1, *2 연산만을 이용해 n이 k가 될 때 까지의 최소 비용을 구하는 문제이다.

*2는 -1,+1과 달리 순간이동이기 때문에 시간이 소요되지 않는 것에 유의해야 한다.

Info 클래스를 생성하여 위치와 시간을 저장하도록 했다.

 

 

🚨CODE

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

/*
 * 구해야하는 것 : n에서 k까지의 최단 시간
 * 움직일 수 있는 방법 : 현재 위치에서 -1, +1, *2
 * 만약 도착지점을 초과한 경우 뒤로 가야하며 이때는 -1 연산밖에 없음 앞으로가는 것은 +1, *2
 * +1, -1은 1초가 소요되나 *2는 0초가 소요된다.
*/
public class Main {
	static int max = 100000;
	static int min = Integer.MAX_VALUE;
	static boolean[] visit = new boolean[max+1];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		Queue<Info> q = new LinkedList<>();
		
		q.offer(new Info(n, 0));
		
		while(!q.isEmpty()) {
			Info info = q.poll();
			int pos = info.pos;
			int time = info.time;
			visit[pos] = true;
			
			if(pos == k) {
				min = Math.min(min, time);
			}
			
			if(pos*2 <= max && !visit[pos*2]) {
				q.offer(new Info(pos*2, time));
			}
			if(pos+1 <= max && !visit[pos+1]) {
				q.offer(new Info(pos+1, time+1));
			}
			if(pos-1 >= 0 && !visit[pos-1]) {
				q.offer(new Info(pos-1, time+1));
			}
			
		}
		
		System.out.println(min);
		
	}
	
}
class Info{
	int time; // 현재까지 걸린 시간
	int pos; // 현재 위치
	
	Info(int curPos, int curTime){
		this.time = curTime;
		this.pos = curPos;
	}
}