[백준] 1753 : 최단경로 - 자바(JAVA)

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

1753번: 최단경로

 

문제 풀이 전 설계

방향 그래프 탐색 문제이며 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 합니다.

정점의 개수가 20,000개 이고 간선의 개수가 300,000이다 보니 완전 탐색은 불가능하고 정점과의 거리를 갱신시키는 다익스트라 알고리즘을 그대로 적용하면 될 것 같습니다.

 

정점의 개수가 많기 때문에 인접행렬보다는 인접 리스트를 이용합니다.

또는 from to 를 가지는 Edge 클래스를 만들어서 사용합니다.

 

모든 간선의 가중치는 10 이하이고 간선의 개수는 300,000이므로 가중치의 최대합은 3,000,000이므로 int형을 사용해도 문제가 없을 것 같습니다.

 

서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 도 있습니다.

이때는 정점을 한번씩 꼭 이용해야 한다는 이야기는 없으므로 가중치가 가장 남은 값만 기록하여 사용하면 됩니다.

다익스트라 알고리즘 이란?

https://junuuu.tistory.com/208?category=987844 

다익스트라(Dijkstra) 알고리즘

 

코드

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

public class Main_1753_최단경로 {

	static boolean[] visited;
	static List<ArrayList<int[]>> edges;
	static int[] DP;
	static int V, E;

	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());

		// 인접 리스트 생성
		edges = new ArrayList<ArrayList<int[]>>();
		for (int i = 0; i <= V; i++) {
			edges.add(new ArrayList<int[]>());
		}

		// 정점의 번호는 1~V번
		int startIndex = Integer.parseInt(br.readLine());
		visited = new boolean[V + 1];
		DP = new int[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());
			edges.get(from).add(new int[] { to, weight });
		}
		// DP 초기값은 무한대로 초기화
		for (int i = 0; i < V + 1; i++) {
			DP[i] = Integer.MAX_VALUE;
		}
		// 자기 자신은 0
		DP[startIndex] = 0;

		// 메인 로직 시작
		dfs();

		// 최단 경로 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < V + 1; i++) {
			if (DP[i] == Integer.MAX_VALUE) {
				sb.append("INF" + "\n");
				continue;
			}
			sb.append(DP[i] + "\n");
		}

		System.out.println(sb);
	}

	private static void dfs() {

		// 방문되지 않은 정점들 중 최솟값 기록
		int currentIndex = Integer.MAX_VALUE;
		int tempValue = Integer.MAX_VALUE;
		for (int i = 1; i < V + 1; i++) {
			if (visited[i]) {
				continue;
			}
			if (tempValue > DP[i]) {
				tempValue = DP[i];
				currentIndex = i;
			}
		}
		
		// 만약에 가장 최솟값인 정점이 INF(무한)이라면 모두 방문되었거나 더이상 탐색할 것이 없으므로 종료
		if (currentIndex == Integer.MAX_VALUE) {
			return;
		}

		visited[currentIndex] = true;

		// startIndex와 연결된 정보들을 활용하여 최단경로 DP 생성
		for (int[] e : edges.get(currentIndex)) {
			// DP에 최단경로 기록
			DP[e[0]] = Math.min(DP[e[0]], e[1]+DP[currentIndex]);
			// 방문되지 않은 정점들 중 최솟값 기록
		}

		dfs();
	}

}