[백준] 1753번 최단경로 (Java)

문제 Gold5

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

1753번: 최단경로

---

풀이

시작점에서 모든 정점까지의 최단경로를 구하는 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘 구현

- 시작점에서부터 방문여부와 시작점부터의 최소 경로 정점을 탐색

- 최소 경로 정점 탐색 후, 해당 정점에 대한 distance배열(해당 정점을 경유해서 갈 수 있는 최단 거리)을 재설정

 

그래프 정보를 처음 인접행렬로 풀었으나 테케의 크기가 매우 크기 때문에 메모리 초과 오류가 났다.

따라서 이를 인접 행렬이 아닌 인접 리스트로 구현하였다.

 

코드

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

class Element{
	int to, weight;
	public Element(int to, int weight) {
		this.to = to;
		this.weight = weight;
	}
}
public class Main{
	public static void main(String[] args) throws Exception{
		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 K = Integer.parseInt(br.readLine());
		
		List<Element>[] adjList = new ArrayList[V+1];
		for(int i =1 ; i < V+1 ; i++) {
			adjList[i] = new ArrayList<>();
		}
		int[] distance = new int[V+1];
		boolean[] visited = new boolean[V+1];
		
		for(int i = 0 ; i < E ; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			adjList[from].add(new Element(to, weight));
		}
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[K] = 0;
		
		int min = 0, current = 1;
		for(int i =1 ; i <= V ; i++) {
			min = Integer.MAX_VALUE;
			for(int j =1  ; j <= V ; j++) {
				if(!visited[j] && distance[j] < min) {
					min = distance[j];
					current = j;
				}
			}
			visited[current] = true;
			for(int j =0 ; j < adjList[current].size() ; j++) {
				if(!visited[adjList[current].get(j).to] && distance[adjList[current].get(j).to] > min+adjList[current].get(j).weight) {
					distance[adjList[current].get(j).to] = min+adjList[current].get(j).weight;
				}
			}
		}
		
		for(int i = 1; i <= V ; i++) {
			if(distance[i] == Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(distance[i]);
		}
	}
}