[최단경로] 백준 13549번 숨바꼭질 3(Java)

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

13549번: 숨바꼭질 3

📚 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

📝 문제 해설

이동하는 위치에 따라 이동시간(가중치)가 다르므로 다익스트라 알고리즘으로 구현함

세 가지 연산에 따라 이동하며 범위를 벗어나지 않는지 확인하고 최솟값으로 갱신해주며 시간을 저장해주면 된다.

 

💻 코드

import java.util.*;

class Node implements Comparable<Node> {
	public int index;		
	public int time;			

	public Node (int index, int time) {
		this.index = index;
		this.time = time;
	}

	public int compareTo(Node n) {
		return this.time - n.time;
	}
}

public class BOJ13549 {
	public static final int INF = (int) 1e9;
	public static int n, k;
	public static int[] d = new int[100001];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		
		Arrays.fill(d, INF);
		 
		dijkstra();
		System.out.println(d[k]);
	}
	
	public static void dijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(n, 0));
		d[n] = 0;
		
		while(!pq.isEmpty()) {
			Node curNode = pq.poll();
			if (d[curNode.index] < curNode.time) continue;
			
			int[] route = new int[] {curNode.index-1, curNode.index+1, curNode.index*2};
			for(int i=0; i<route.length; i++) {
				if(route[i] < 0 || route[i] > 100000) continue;
				
				Node nextNode = new Node(route[i], (i == 0 || i == 1) ? 1 : 0);
				if(d[nextNode.index] > d[curNode.index] + nextNode.time) {
					pq.offer(nextNode);
					d[nextNode.index] = d[curNode.index] + nextNode.time;
				}
			}
		}
	}
}

💡 아이디어
연산을 배열에 저장해놓고 해당 연산으로 이동할 때의 시간이 더 적은 경우 시간 갱신 및 우선순위 큐에 추가해준다.

 

[참고 : https://velog.io/@silver_star , 

           https://yoonbing9.tistory.com/73]