[백준 - Java] 1916번 : 최소비용 구하기

문제

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

1916번: 최소비용 구하기

설명

다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제다.

 

📌 다익스트라 알고리즘에 대해 알고 싶다면 아래 포스팅을 확인해주세요.

 

[Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘

전체 코드

* 무한대를 처음엔 Integer.MAX_VALUE로 했는데 오버플로우가 나는지 채점 중 런타임 에러가 났다ㅠㅠ

무한대 값을 Integer.MAX_VALUE-1 로 하면 안남...왜지?

 

* 백준 사이트에서 알아본 결과

INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값을 사용해야 합니다. 

거리가 가장 멀어지는 경우를 생각해 보면, 1-2-3-4-5-6-...-V 이렇게 일직선으로 모든 간선이 최대 가중치를 가지고 연결되어 있을 때 

총 V-1개의 간선을 전부 차례대로 지나가야 하기 때문입니다. 

 

따라서 무작정 Integer.MAX_VALUE처럼 제일 큰 값 말고 int INF = 100000 * (N-1); 와 같이 INF를 설정 후 푸는 것이 좋을 것 같다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		int[][] arr = new int[N+1][N+1];
		for(int i = 1; i < N+1; i++) {
			Arrays.fill(arr[i], -1); // 가중치 0이 있을수도 있으니 -1로 초기화 
		}

		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int d = sc.nextInt();
			int c = sc.nextInt();

			// 시작 정점과 도착 정점이 같은데 비용이 다른 값이 들어올 수 있기 때문에 예외 처리 
			if(arr[a][d] == -1) 
				arr[a][d] = c;
			else if(arr[a][d] > c) 
				arr[a][d] = c;
		}

		int start = sc.nextInt();
		int end = sc.nextInt();

		boolean[] check = new boolean[N+1]; // 정점이 집합 S에 속하는지 아닌지를 판별할 배열 

		int[] distance = new int[N+1]; // 최단 거리를 담을 배열 
		Arrays.fill(distance, Integer.MAX_VALUE-1); // 무한대로 초기화 

		distance[start] = 0;

		for(int i = 0; i < N-1; i++) { // 시작점을 넣고 시작하기 때문에 N-1만큼만 반복 
			int min = Integer.MAX_VALUE;
			int index = -1;

			// 집합 S에 속하지 않는 가장 최단 거리를 갖는 정점 선택함 
			for(int j = 1; j < N+1; j++) { 
				if(!check[j] && distance[j] < min) {
					min = distance[j]; // 최단 거리 
					index = j; // 최단 거리를 갖는 정점의 index 
				}
			}

			check[index] = true;

			// S에 속하지 않는다면 더 작은 값을 갖는 거리로 distance값 갱신 
			for (int j = 1; j < N+1; j++) { 
				if (!check[j] && arr[index][j] != -1 && distance[index] + arr[index][j] < distance[j]) { // 간선이 연결되지 않은 -1의 경우 역시 제외해야함 
					distance[j] = distance[index] + arr[index][j];
				}
			}
		}

		System.out.println(distance[end]); // 도착점까지의 최단 거리 출력 
	}

}

GITHUB

 

KwonMinha/BOJ