[백준] 13549 : 숨바꼭질 3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

다익스트라(한 노드에서부터 모든 노드까지의 최단 경로 구하기)를 공부할 수 있던 문제였다. DP도 복습하면서 풀었음.

아직 BFS와 DFS의 활용문제가 잘 감이 오지 않는다.

 

내 코드

메모리 : 18488 KB

시간 : 160 ms

코드길이 : 1499 B

 

[내 코드]

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.StringTokenizer;

public class Main {
	static int N;
	static int K;
	static int result = Integer.MAX_VALUE;
    //해당 위치까지 가는 데에 걸리는 최소시간을 저장할 DP
	static int[] time = new int[100001];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		Arrays.fill(time, Integer.MAX_VALUE);
		
		if(N == K)
			result = 0;
		else {
			findSister();
		}
		
		sb.append(result);
		System.out.print(sb);
	}
	
	public static void findSister() {
		Queue<Integer> queue = new LinkedList<>();
		time[N] = 0;
		queue.add(N);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			//동생을 잡으면
			if(now == K) {
				result = time[K];
				return;
			}
			//앞으로 걷기
			if(now + 1 <= 100000 && time[now] + 1 < time[now + 1]) {
				time[now + 1] = time[now] + 1;
				queue.add(now + 1);
			}
			//뒤로 걷기
			if(now - 1 >= 0 && time[now] + 1 < time[now - 1]) {
				time[now - 1] = time[now] + 1;
				queue.add(now - 1);
			}
			//순간이동
			if(2 * now <= 100000 && time[now] < time[2 * now]) {
				time[2 * now] = time[now];
				queue.add(2 * now);
			}
		}
		return;
	}

}