백준 13549 - 숨바꼭질 3

Java

13549 번 - 숨바꼭질 3

문제

접근 방법

BFS + DP로 해결하였다.
만약 순간이동이 1초 이상 이면 처음 도달한 그 위치가 즉 가장 빨리 도착한 시간이지만,
순간이동이 0초 이므로, 이후에 더 빨리 도달할 수가 있다.
따라서, DP를 통해 각 위치에 도달 할 때 이전에 도달한 시간 보다 빠를 때만 시간을 갱신하고 queue에 push하는 방법으로 BFS를 해결한다.

또한 차후에 더 짧은 시간에 도착할 수 있다는 점에서, 결과 k에 도달하더라도 종료하지 않는다.

4 6
정답: 1(4->3->6)

위의 예와 같이, 만약 도착하자마자 종료하면 4->5->6으로 2가 정답이 되지만,
순간이동은 시간이 0이기 때문에 정답이 1이 될 수가 있다.

코드

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

public class Main {
	static int n, k, result = 9999999;
	static int INF = 999999999;
	static int[] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	
    	dp = new int[100001];
    	Arrays.fill(dp, INF);
    	
    	BFS();
    	if(n == k) {
    		result = 0;
    	}
    	System.out.println(result);
    	
    	br.close();
	}
	
	static void BFS() {
		
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {n, 0});
		dp[n] = 0;
		int[] q;
		int curN, time;
		while(!queue.isEmpty()) {
			q = queue.poll();
			curN = q[0];
			time = q[1];
			// 도착 점에 도달하였더라도, 종료하지 않는다.
			// 만약 이후에 한번 더 도달하면, 그 말은 더 빠른 시간에 도달한 것이기 때문이다.
			if(curN == k) {
				result = time;
			}
			
			if(curN + 1 <= 100000 && time + 1 < dp[curN + 1]) {
				queue.add(new int[] {curN + 1, time + 1});
				dp[curN + 1] = time + 1;
			}
				
			if(curN - 1 >= 0 && time + 1 < dp[curN - 1]) {
				queue.add(new int[] {curN - 1, time + 1});
				dp[curN - 1] = time + 1;
			}
			
			if(curN * 2 <= 100000 && time < dp[curN * 2]) {
				queue.add(new int[] {curN * 2, time});
				dp[curN * 2] = time;
			}
		}
	} 
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점