[JAVA][백준][다익스트라 알고리즘][Priority Queue] 1753. 최단경로

1753. 최단경로

1753번: 최단경로

 

• 내 풀이 - HashMap 이용
  • key: 시작정점 값 / value: Pair( 도착정점 값, 가중치값)

package day18_dijkstra;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class JUN1753_ParkSomin {
    static final int INF=Integer.MAX_VALUE;
    static int V, E;
    static HashMap<Integer,ArrayList<Pair>> map;
    static int[] distance;
    static boolean[] visited;

    static class Pair {
        int i, w;

        Pair(int i, int w) {
            this.i = i;
            this.w = w;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V=Integer.parseInt(st.nextToken());
        E=Integer.parseInt(st.nextToken());

        int start=Integer.parseInt(br.readLine());

        distance=new int[V+1];
        Arrays.fill(distance, INF);
        visited=new boolean[V+1];

        map=new HashMap<>();
        for (int i = 1; i < V + 1; i++) {
            map.put(i, new ArrayList<>());
        }


        for (int i = 0; i < E; i++) {
            st=new StringTokenizer(br.readLine());
            //from-> to 로 가는 가중치 w
            int from=Integer.parseInt(st.nextToken());
            int to=Integer.parseInt(st.nextToken());
            int w= Integer.parseInt(st.nextToken());

            map.get(from).add(new Pair(to, w));
        }

        distance[start]=0;

        int min,current;
        for (int i = 1; i < V+1; i++) {
            current=-1;
            min=INF;
            for (int j = 1; j < V+1; j++) {
                if(!visited[j] && min>distance[j]){
                    min=distance[j];
                    current=j;
                }
            }

            if(current==-1) break;



            visited[current]=true;
            for (Pair p: map.get(current)) {
                if (!visited[p.i] && p.w!=0 && distance[p.i]> min+p.w){
                    distance[p.i]= min+p.w;
                }
            }
        }

        for (int i = 1; i < V+1; i++) {
            System.out.println(distance[i]!=INF ? distance[i]: "INF" );
        }

    }
}

 

• 다른 사람풀이 - Priority Queue 이용
  
  • 우선순위큐에서는 pq.poll() 하면 자동으로 최소값이 나오기 때문에 
  • 최소값 찾기위한 for문을 돌 필요가 없다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
import java.util.PriorityQueue;

class Pair implements Comparable<Pair>{
	int dst;
	int weight;
	
	Pair(int dst, int weight){
		this.dst= dst;
		this.weight = weight;
	}
	
	@Override
	public int compareTo(Pair o) {
		return this.weight - o.weight;
	}

}

public class JUN1753_ParkYeongseo {
	static int INF = Integer.MAX_VALUE;
	static PriorityQueue<Pair> pq = new PriorityQueue<>();
	static List<List<Pair>> adj = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int V, E, K, u, v, w;
	
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine());	
		
		for (int i = 0; i <= V; i++) adj.add(new ArrayList<>());
		
		int dist[] = new int[V + 1];
		Arrays.fill(dist, INF);
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());		
			adj.get(u).add(new Pair(v, w));
		}
		
		pq.add(new Pair(K, 0));
		
		while (!pq.isEmpty()) {
			Pair top = pq.poll();
			int topDst = top.dst;
			int topWeight = top.weight;
			if (dist[topDst] != INF) continue;
			dist[topDst] = topWeight;
			
			for (Pair next : adj.get(topDst)) {
				int nextDst = next.dst;
				int nextWeight = next.weight + topWeight;
				if (dist[nextDst] != INF) continue;
				pq.add(new Pair(nextDst, nextWeight));
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= V; i++) {
			if (dist[i] == INF) sb.append("INF\n");
			else sb.append(dist[i] + "\n");
		}
		
		System.out.println(sb);
	}
	
}