boj 1916: 최소비용 구하기

• 최단경로를 구하는 알고리즘
  • 다익스트라 알고리즘: 모든 간선에 대해 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]);
	}
}