[BaekJoon] 백준 1753번 최단경로

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

1753번: 최단경로

 

다익스트라의 개념을 물어보는 문제입니다.

다만 인접행렬이 아닌 인접리스트, 단순반복이 아닌 우선순위큐를 사용하여 풀어야 시간초과, 메모리 부족이 일어나지 않습니다.

 

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

public class Main {
	static class Vertex implements Comparable<Vertex>{
		int vertex;
		int distance;
		
		public Vertex(int v, int d) {
			this.vertex = v; this.distance = d;
		}
		public void setWDist(int d) {
			this.distance = d;
		}	
		
		@Override
		public int compareTo(Vertex v) {
			if(this.distance > v.distance)
				return 1;
			else
				return -1;
		}
	}
	static class Edge {
		int veretx;
		int weight;
		public Edge(int v, int w) {
			this.veretx = v; this.weight = w;
		}
	}
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String[] input = br.readLine().split(" ");
			int V = Integer.parseInt(input[0]);
			int E = Integer.parseInt(input[1]);
			ArrayList<Edge>[] edge = new ArrayList[V+1];
			
			int[] distance = new int[V+1];
			Arrays.fill(distance,  Integer.MAX_VALUE);
			
			for(int i = 1; i<=V; i++) {
				edge[i] = new ArrayList<>();
			}
			
			int start = Integer.parseInt(br.readLine());
			distance[start] = 0;
			
			for(int i = 0; i<E; i++) {
				String[] query = br.readLine().split(" ");
				int u = Integer.parseInt(query[0]);
				int v = Integer.parseInt(query[1]);
				int w = Integer.parseInt(query[2]);
				
				edge[u].add(new Edge(v, w));	
			}
			
			PriorityQueue<Vertex> p = new PriorityQueue<Vertex>();
			
			p.offer(new Vertex(start, distance[start]));
			
			while(!p.isEmpty()) {
				Vertex curr = p.poll();
				if(curr.distance > distance[curr.vertex])
					continue;
				
				for(Edge e : edge[curr.vertex]) {
					if(distance[e.veretx] > curr.distance + e.weight) {
						distance[e.veretx] = curr.distance + e.weight;
						p.offer(new Vertex(e.veretx, distance[e.veretx]));
					}
				}
			}
			
			for(int i = 1; i<=V; i++) {
				if(distance[i] == Integer.MAX_VALUE)
					System.out.println("INF");
				else
					System.out.println(distance[i]);
			}
		}catch(IOException e) {	
		}
	}
	
}

 

우선순위큐에 들어갈 정점 정보 Vertex, 인접리스트에 사용될 간선 입력 정보인 Edge를 만들어 사용했습니다.

Vertex의 distance는 시작정점 부터 해당 정점까지의 거리입니다. (최단거리x)

 

distance를 Integer.MAX_VALUE로 초기화합니다. 

시작 정점은 distance를 0으로 합니다. 

 

큐에 저장된 정점을 빼서 Vertex.distance와 distance[]를 비교하여 작은 경우 연결된 모든 간선을 검사하며 weight와 더하고 비교하여 최단거리를 갱신합니다.

 

갱신된 정점은 큐에 새롭게 삽입되어 다시 최단거리를 계산합니다.