BOJ 1916 : 최소비용 구하기 - https://www.acmicpc.net/problem/1916
A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키는게 목적이기 때문에, A가 출발지가 되어 다른 도시까지의 최소 경로를 구해야 한다. Dijkstra Algorithm
을 사용한다.
<다익스트라 알고리즘 구현>
dist[]
로 선언하여 초기화한다. 가는 길이 존재한다면 해당 weight
를, 경로가 존재하지 않으면 무한대
(Integer.MAX_VALUE-1) 값으로 초기화한다.visited[]
를 선언한다.index
를 가져온다.index
를 visited 처리 한 뒤, 그 index의 도시를 거쳐가는 경로가 원래 dist[]에 들어있는 값보다 작으면 값을 변경한다.import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static long[] dist;
static boolean[] visited;
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(i==j) {
map[i][j] = 0;
continue;
}
map[i][j] = Integer.MAX_VALUE-1; // infinite
}
}
for (int i = 0; i < m; i++) {
String[] inputs = br.readLine().split(" ");
int s = Integer.parseInt(inputs[0]);
int e = Integer.parseInt(inputs[1]);
int w = Integer.parseInt(inputs[2]);
// 같은 경로가 여러 번 들어올 경우 가장 작은 weight 값을 저장
if(map[s][e] == -1)
map[s][e] = w;
else if(map[s][e] > w)
map[s][e] = w;
}
String[] inputs = br.readLine().split(" ");
int start = Integer.parseInt(inputs[0]);
int end = Integer.parseInt(inputs[1]);
dist = new long[n + 1];
visited = new boolean[n + 1];
// Dijkstra
// distance initialize
for (int i = 1; i <= n; i++) {
dist[i] = map[start][i];
}
visited[start] = true;
for (int i = 0; i < n - 1; i++) {
int cur = getMinIdx();
visited[cur] = true;
for (int j = 1; j <= n; j++) {
if(!visited[j]){
if (dist[cur] + map[cur][j] < dist[j]) { // 거쳐가는게 더 빠르면 갱신
dist[j] = dist[cur] + map[cur][j];
}
}
}
}
System.out.println(dist[end]);
}
public static int getMinIdx() {
long min = Integer.MAX_VALUE;
int idx = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] < min && !visited[i]) {
min = dist[i];
idx = i;
}
}
return idx;
}
}
✔ 알고리즘 분류 - 그래프 이론, 다익스트라
✔ 난이도 - 🟡 Gold 5
https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221234424646&redirect=Dlog&widgetTypeCall=true&directAccess=false (Dijkstra Algorithm)