공부 기록

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

인접 행렬로 풀면 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번 들어갔다가 나오는 시간이 걸린다.

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

가능한 경로 2가지

• 1 -> v1 -> v2 -> N
• 1 -> v2 -> v1 -> N

다익스트라 알고리즘을 시작점 1, v1, v2로 하여 각각 구한뒤 더했을 때 최솟값을 구하도록 한다

import java.util.*;

public class Main {
	public static long MAX = 800 * 200000 * 1000 + 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int e = 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);
			mat[end][start] = Math.min(mat[end][start], weight);
		}

		int v1 = in.nextInt();
		int v2 = in.nextInt();

		long distFrom1[] = dijkstra(1, n, mat);
		long distFromV1[] = dijkstra(v1, n, mat);
		long distFromV2[] = dijkstra(v2, n, mat);

		long ans = -1;
		// 갈 수 없는 경우 체크
		if (distFrom1[v1] < MAX && distFromV1[v2] < MAX && distFromV2[n] < MAX) {
			ans = distFrom1[v1] + distFromV1[v2] + distFromV2[n];
		}
		if (distFrom1[v2] < MAX && distFromV2[v1] < MAX && distFromV1[n] < MAX) {
			ans = Math.min(ans, distFrom1[v2] + distFromV2[v1] + distFromV1[n]);
		}
		System.out.println(ans);
	}

	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;
	}
}

2020/07/07 - [알고리즘 공부] - boj 1916: 최소비용 구하기

위의 풀이와 똑같지만, 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력하기 위해서는

경로의 최솟값이 업데이트 될 때의 위치를 저장하도록 하면 된다.

마지막에 답을 구할 때에는 이전 위치를 저장하도록 했으므로

도착지점->시작지점 순으로 스택에 넣고 빼면서 프린트 한다.

import java.util.*;

public class Main {
	public static int MAX = 1000000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int bus[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(bus[i], MAX);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();

			bus[start][end] = Math.min(bus[start][end], time);
		}

		int start = in.nextInt();
		int end = in.nextInt();
		int dist[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];
		int route[] = new int[n + 1];
		Arrays.fill(route, start);
		Arrays.fill(dist, MAX);
		for (int i = 1; i <= n; i++) {
			dist[i] = bus[start][i];
		}
		dist[start] = 0;
		route[start] = 0;
		isVisited[start] = true;

		for (int i = 1; i < n; i++) {

			int index = -1;
			int 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] + bus[index][j]) {
					dist[j] = dist[index] + bus[index][j];
					route[j] = index;
				}
			}

		}
		
		System.out.println(dist[end]);
		Stack<Integer> answerSet=new Stack<Integer>();
		int now=end;
		while(true) {
			if(now==start) {
				answerSet.add(now);
				break;
			}
			
			answerSet.add(now);
			now=route[now];
		}
		
		System.out.println(answerSet.size());
		while(!answerSet.isEmpty()) {
			System.out.print(answerSet.pop()+" ");
		}
	}
}

• 최단경로를 구하는 알고리즘
  • 다익스트라 알고리즘: 모든 간선에 대해 1번만 검사
  • 모든 정점을 선택(V-1)하고, isVisited==false인 값 중에서 가장 가까운 값을 선택하는데 걸리는 시간은 O(V): 총 O(V^2)
  • 음수가 있을 때 사용할 수 없다
  • 정점을 처리했는지 안했는지 체크해야한다 (isVisited)

c.f. 벨만 포드 알고리즘: 식을 N-1번 검사, 음수가 있을 때 사용 가능

맨 처음 풀이에서 isVisited==false인 값 중 가장 가까운 값을 선택할 때

min=MAX로 초기화 하고 min을 업데이트 해 나갔을 때에는 런타임 에러가 발생했다.

그래서 index가 업데이트 되지 않을 때 런타임 에러가 발생하므로 index==-1인 경우 따로 break문을 추가했다.

이 외에도 min=MAX+1으로 설정하면 break문 없이 정답이 나온다.

처음에는 Integer.MAX_VALUE로 MAX를 설정했는데, 오버플로우 등이 일어나서

비용 범위가 100000까지고 노드가 최대 1000개이므로 최대 INF를 1000000000로 잡았다.

import java.util.*;

public class Main {
	public static int MAX = 1000000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int bus[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(bus[i], MAX);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();

			bus[start][end] = Math.min(bus[start][end], time);
		}

		int start = in.nextInt();
		int end = in.nextInt();
		int dist[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];
		Arrays.fill(dist, MAX);
		for (int i = 1; i <= n; i++) {
			dist[i] = bus[start][i];
		}
		dist[start] = 0;
		isVisited[start] = true;

		for (int i = 1; i < n; i++) {

			int index = -1;
			int 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] + bus[index][j]) {
					dist[j] = dist[index] + bus[index][j];
				}
			}

		}
		System.out.println(dist[end]);
	}
}