[백준] 13549번 (java 자바)

import java.util.*;

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

public class Main
{   
    static final int MAX_N = 100000;
    static int[] visited;
    static PriorityQueue<Node> q = new PriorityQueue<>((a, b)->a.time - b.time);
    
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		visited = new int[100001];
		
		q.add(new Node(N, 1));
		
		visited[N] = 1;
		
		while(!q.isEmpty()){
		    Node curr = q.poll();
		    
		    if(curr.end == K){
		        System.out.println(curr.time - 1);
		        break;
		    }
		    
		    if(curr.end + 1 >= 0 && curr.end + 1 <= MAX_N){
		        if(visited[curr.end + 1] == 0 || visited[curr.end + 1] > curr.time + 1){
		            visited[curr.end + 1] = curr.time + 1;
		            q.add(new Node(curr.end + 1, curr.time + 1));
		        }
		    }
		    if(curr.end - 1 >= 0 && curr.end - 1 <= MAX_N){
		        if(visited[curr.end - 1] == 0 || visited[curr.end - 1] > curr.time + 1){
		            visited[curr.end - 1] = curr.time + 1;
		            q.add(new Node(curr.end - 1, curr.time + 1));
		        }
		    }
		    if(curr.end * 2 >= 0 && curr.end * 2 <= MAX_N){
		        if(visited[curr.end * 2] == 0 || visited[curr.end * 2] > curr.time){
		            visited[curr.end * 2] = curr.time;
		            q.add(new Node(curr.end * 2, curr.time));
		        }
		    }
		}
		
	}
}

 

우선순위 큐를 사용해서 

먼저 K에 도착하면 바로 출력하도록 했다

 

다익스트라 특징 중 하나는

최단 경로의 부분 경로도 최단 경로임을 떠올렸다 (이를 위해 우선순위 큐 사용)