[BOJ-1753][다익스트라] 최단경로 -Java

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

1753번: 최단경로

package algo;

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

public class boj_1753_최단경로 {
	static class Node{
		int end;
		int weight;
		public Node(int end, int weight) {
			this.end = end;
			this.weight = weight;
		}
	}
	static int V,E;
	static int [] minEdge;
	static boolean [] visited;
	static List<Node>[] list;
	static String [] result;
	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());
		
		minEdge=new int[V+1];
		result=new String[V+1];
		list = new List[V+1];
		visited=new boolean[V+1];
		
		Arrays.fill(minEdge, Integer.MAX_VALUE);
		for(int i=0; i<=V; i++){
			list[i]=new ArrayList<Node>();
		}
		
		int startVertex = Integer.parseInt(br.readLine());
		minEdge[startVertex]=0;
		
		for(int i=0; i<E; i++) {
			 st = new StringTokenizer(br.readLine());
			 int start=Integer.parseInt(st.nextToken());
			 int end=Integer.parseInt(st.nextToken());
			 int weight=Integer.parseInt(st.nextToken());
			 list[start].add(new Node(end,weight));
		}
		
		solve(startVertex);
		for(int i=1; i<=V; i++) {
			System.out.println(result[i]);
		}
		
	}
	private static void solve(int startVertex) {
		PriorityQueue<Node> pq =new PriorityQueue<>((o1,o2)->(o1.weight-o2.weight));
		pq.add(new Node(startVertex, 0));
		
		while(!pq.isEmpty()) { //pq가 빌 때 까지 
			Node cur = pq.poll();
			int curVertex=cur.end;
			int curWegiht=cur.weight;
			visited[curVertex]=true;
			
			//현재 정점을 기준으로 쭉 탐색
			for(int i=0; i<list[curVertex].size(); i++) {
				Node node=list[curVertex].get(i);
				if(visited[node.end]) { //현재 방문 했으면 continue
					continue;
				}
				
				if(minEdge[node.end]>minEdge[curVertex]+node.weight) {
					minEdge[node.end]=minEdge[curVertex]+node.weight;
					pq.offer(new Node(node.end,minEdge[node.end] ));
				}
			}
		}
		
		for(int i=1; i<=V; i++) {
			String distance= minEdge[i]==Integer.MAX_VALUE? "INF" : Integer.toString(minEdge[i]); 
			result[i]=distance;
		}
	}

}

소요시간 : 27분

 

우선순위 큐를 이용한 다익스트라 코드입니다.

문제를 읽었을 때 주어진 시작점에서 모든 정점으로 최단경로를 구해라.

 

로직을 설펴보면

 

1. start하는 정점의 가중치를 0으로 바꿔줍니다. + 우선순위 큐에 넣어줍니다.

2. 큐에서 Node하나를 뺍니다.

3. Node와 연결된 모든 정점을 돌면서 최단거리를 갱신해 줍니다.

4. 만약 최단거리의 갱신이 일어났다면 우선순위 큐에 넣어줍니다.

 

다익스트라 알고리즘만 알고 있다면 쉽게 풀 수 있는 문제이기 때문에 길게 설명하지 않겠습니다

 

끝~