boj 1753: 최단경로

아래와 같이 다른 다익스트라 문제와 동일하게 풀었는데 메모리 초과 및 시간초과가 나왔다.

인접 행렬로 풀면 V==20000일 때 인접행렬은 4억개이고 정수형이니 각 크기가 8B면 3200 MB가 되어서 그렇다고 함,,,

import java.util.*;

public class Main {
	public static long MAX = 20000 * 300000 * 10 + 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int e = in.nextInt();
		int startPoint = in.nextInt();
		long mat[][] = new long[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], MAX);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long weight = in.nextLong();

			mat[start][end] = Math.min(mat[start][end], weight);
		}

		long dist[] = dijkstra(startPoint, n, mat);
		for (int i = 1; i <= n; i++) {
			if (dist[i] >= MAX) {
				System.out.println("INF");
			} else {
				System.out.println(dist[i]);
			}
		}
	}

	public static long[] dijkstra(int startPoint, int n, long mat[][]) {
		long[] dist = new long[n + 1];
		boolean[] isVisited = new boolean[n + 1];

		Arrays.fill(dist, MAX);

		for (int i = 1; i <= n; i++) {
			dist[i] = mat[startPoint][i];
		}
		dist[startPoint] = 0;
		isVisited[startPoint] = true;

		for (int i = 1; i < n; i++) {
			int index = -1;
			long min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}

			if (index == -1) {
				break;
			}
			isVisited[index] = true;

			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + mat[index][j]) {
					dist[j] = dist[index] + mat[index][j];
				}
			}

		}

		return dist;
	}
}

 

그리고 V<=20000이기 때문에 시간복잡도 O(V^2)로는 4억(약 4초)가 걸린다.

다익스트라 알고리즘을 구하는 순서를 다시 보면 아래와 같다.

1. 체크되어 있지 않은 정점 중에서 D의 값이 가장 작은 정점 index 를 선택한다. : O(V)
2. index틑 체크한다.
3. index와 연결된 모든 정점에 대해 최단거리 갱신: 인접행렬의 경우 O(V^2), 인접리스트의 경우 O(V+E)

여기서 시간을 줄일 수 있는 부분은 1번이다.

(정점 번호, Dist)값을 heap이나 priorityQueue에 넣어서 가장 작은 정점을 선택할 수 있도록 한다.

이떄 시간복잡도는 모든 간선이 들어가는 것이나 마찬가지이다.

왜냐면 dist배열이 업데이트 될때마다 들어가는데, 업데이트 된다는 것의 의미는

어떤 정점에 연결되어 있는 간선에 대해 비교를 한 것과 같다.

따라서 O(ElogE), 즉 (정점 번호, Dist)쌍이 E번 들어갔다가 나오는 시간이 걸린다.

 

위 풀이를 적용하여 다시 문제를 풀어볼 예정