[백준 15971] 두 로봇 (Java)

문제 링크: www.acmicpc.net/problem/15971

15971번: 두 로봇

1. 주의할 점

- 다익스트라 알고리즘에 대해 알고 있어야 한다

- O(NlgN)에 끝내도록 한다

 

2. 구현

- 같은 통로에 있을때까지 이동한다

→ A에서 B까지 이동한다 - 1개의 변을 뺀다

→ 빼는 1개의 변이 최단경로중 가장 값이 크면 움직인 거리가 최소가 된다

→ 다익스트라 알고리즘 + 변의 최장 길이 저장

- Dist[] 배열을 통해 시작지점에서 각 지점까지의 최단거리를 저장한다

- Li[] 구조체 배열을 통해 모든 간선에 대한 정보를 저장한다

- 위 2개의 배열을 초기화하고 시작한다

- 우선순위 큐를 이용한 다익스트라 알고리즘을 구현하여 O(NlgN)안에 수행되도록 한다. 이때. CompareTo() 함수를 Override하고 아래와 같이 설정하여 우선순위큐가 최단경로순으로 정렬되도록 한다

- Dist[]가 갱신이 되어 우선순위큐에 새로운 원소를 넣을때마다 Maxi변수에는 경로중에서 변의 최장길이가 저장되도록 한다

- 도착지점에 도달한 경우, 최단경로 - Maxi값을 Result에 할당하고 다익스트라 알고리즘을 종료한다

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

public class Main {
	static class Info implements Comparable<Info>{
	    int idx, val, maxi;
	    public Info(int idx, int val, int maxi){
	        this.idx = idx;
	        this.val = val;
	        this.maxi = maxi;
	    }
	    @Override
	    public int compareTo(Info o){
	        return Integer.compare(this.val,o.val);
	    }
	};
	
	static int dist[];
	static int node,s,t,a,b,val,result;
	static List<Info> li[];
	static Info ii;
	
	static void dijkstra(){
	    PriorityQueue<Info> pq = new PriorityQueue<>();
	    pq.offer(new Info(s,0,0));
	    while(!pq.isEmpty()){
	        ii = pq.poll();
	        int cidx = ii.idx;
	        int cv = ii.val;
	        int cmaxi = ii.maxi;
	        if(cidx==t){
	            result = cv-cmaxi;
	            break;
	        }
	        for(int i=0;i<li[cidx].size();i++){
	            int next = li[cidx].get(i).idx;
	            int nv = li[cidx].get(i).val;
	            if(dist[next]>cv+nv){
	                dist[next]=cv+nv;
	                pq.offer(new Info(next,cv+nv,Math.max(cmaxi,nv)));
	            }
	        }
	    }
	}
	
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String ss = br.readLine();
	    StringTokenizer st = new StringTokenizer(ss);
	    node = Integer.parseInt(st.nextToken());
	    s = Integer.parseInt(st.nextToken());
	    t = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    dist = new int[node+1];
	    li = new List[node+1];
	    for(int i=1;i<=node;i++){
	        li[i] = new ArrayList<>();
	        dist[i]=Integer.MAX_VALUE;
	    }
	    
	    for(int i=0;i<node-1;i++){
	        ss = br.readLine();
	        st = new StringTokenizer(ss);
	        a = Integer.parseInt(st.nextToken());
	        b = Integer.parseInt(st.nextToken());
	        val = Integer.parseInt(st.nextToken());
	        li[a].add(new Info(b,val,0));
	        li[b].add(new Info(a,val,0));
	    }	    
	    dijkstra();
	    System.out.print(result);
	}
}