[백준][1753][자바] 최단경로

www.acmicpc.net/problem/1753

1753번: 최단경로

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(br.readLine())-1;
		List<List> list = new ArrayList<>();
		
		for(int i=0; i<V; i++) {
			list.add(new ArrayList<Data>());
		}
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			int e = Integer.parseInt(st.nextToken());
			
			List data = list.get(x);
			
			data.add(new Data(y,e));
		}
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[V];
		int[] distance = new int[V];
		
		//초기값 무한대로 설정
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		//첫번째 노드 넣어주기
		pq.add(new Vertex(start,0));
		distance[start] = 0;
		
		Vertex current = null;
		
		while(!pq.isEmpty()) {
			// 방문하지 않은 정점들 중에 출발지에서 자신까지 오는 비용이 최단인 정점을 고려할 경유지로 선택
			current = pq.poll();
			
			//이미 처리가 끝남
			if(visited[current.no]) continue;
			
			//visited는 처리가 끝난 정점을 검사하는거라 꺼내는 순간에 true
			visited[current.no] = true;
			
			//current 정점을 경유지로 해서 아직 방문하지 않은 다른 정점으로의 최단거리 비용 계산하여 유리하면 update
			List tmp = list.get(current.no);
			for(int i=0; i<tmp.size(); i++) {
				Data data = (Data) tmp.get(i);
				if(distance[data.end] > current.totalInstance + data.wight 
						&& !visited[data.end]) {
					distance[data.end] = current.totalInstance + data.wight ;
					pq.add(new Vertex(data.end, distance[data.end]));
				}
			}
		}
		
		//distance 찍어주기
		for(int i=0; i<distance.length; i++) {
			if(distance[i] == Integer.MAX_VALUE)System.out.println("INF");
			else System.out.println(distance[i]);
		}
		
	}
	
	static class Vertex implements Comparable<Vertex>{
		int no;
		int totalInstance;
		public Vertex(int Vertex, int totalInstance) {
			super();
			this.no = Vertex;
			this.totalInstance = totalInstance;
		}
		@Override
		public int compareTo(Vertex o) {
			// totalDistance가 작은 비용이 우선적으로 처리
			return this.totalInstance - o.totalInstance;
		}
	}
	
	static class Data{
		int end;
		int wight;
		
		public Data(int end, int wight) {
			super();
			this.end = end;
			this.wight = wight;
		}
	}
}

정리

1. 인접행렬로 하면 V값이 20000 이기 때문에 메모리 초과가 난다. 간선 정보를 인접리스트에 저장한다.
2. 최단경로 값을 저장하는 배열을 무한대(Intger.MAX_VALUE)로 초기화 시켜준다.
3. 우선순위 큐를 통해 최소값을 가지는 정점을 뽑아낸다.
4. 이미 검사가 끝난 정점이면 넘어가고 꺼낸 순간에 visited를 true로 해준다.
5. 현재 정점을 경유지로 해서 아직 방문하지 않은 다른 정점으로의 최단거리 비용 계산하여 유리하면 update한다.