백준 1753 최단경로 [JAVA]

1753번: 최단경로

 

풀이 방법

i번 정점으로의 최단 경로를 구하는 문제였습니다.

 

해당 간선의 정보를 list[]에 넣어주었습니다. 우선순위 큐를 이용해 가중치가 작은 간선부터 탐색을 시작했습니다.

시작점에서 연결된 간선 중 아직 방문하지 않았으며 해당 정점으로 바로가는 것보다 다른 곳을 거쳐 도착하는 거리가 더 짧으면 distance 배열에 거리를 변경해주고 간선 정보를 큐에에 넣어 이와 같은 과정을 반복해주었습니다.

 

 

[아래 링크는 다른 방법으로 푼 1753번 최단경로]

백준 1753번 최단경로 [JAVA]

[다른 방법으로 푼 1753번 최단경로]

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_BJ_1753_최단경로_PQ {
    
    static class info implements Comparable<info>{
        int end, weight;
 
        public info(int end, int weight) {
            super();
            this.end = end;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(info o) {
            return this.weight-o.weight;
        }
        
    }
    
    static int V,E;
    static int [] distance;
    static ArrayList<info> node[];
    static boolean [] visited;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        
        st = new StringTokenizer(br.readLine());
        
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        distance = new int[V+1];
        node = new ArrayList[V+1];
        visited = new boolean[V+1];
        
        for(int i=1;i<distance.length;i++) node[i] = new ArrayList<>();
        
        int start = Integer.parseInt(br.readLine());
        
        for(int i=1;i<distance.length;i++) distance[i] = Integer.MAX_VALUE;
        distance[start] = 0;
        
        for(int i=0;i<E;i++) {
            st = new StringTokenizer(br.readLine());
            
            int go = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            
            node[go].add(new info(end,value));
        }
        
        dijkstra(start);
        
        for(int i=1;i<distance.length;i++) {
            if(distance[i]==Integer.MAX_VALUE) sb.append("INF\n");
            else sb.append(distance[i]+"\n");
        }
        System.out.println(sb.toString());
 
    }
    
    public static void dijkstra(int start) {
        PriorityQueue<info> pq = new PriorityQueue<>();
        pq.add(new info(start,0));
        
        while(!pq.isEmpty()) {
            info temp = pq.poll();
            
            if(!visited[temp.end]) {
                for(info item : node[temp.end]) {
                    if(distance[item.end]> distance[temp.end]+item.weight) {
                        distance[item.end]=distance[temp.end]+item.weight;
                        pq.add(new info(item.end,distance[item.end]));
                    }
                }
                visited[temp.end] = true;
            }
        }
        
    }
 
}