https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static int V;
public static ArrayList<Node>[] adjacentList;
public static int[] table;
public static HashSet<Integer> set = new HashSet<>();
public static boolean[] visited;
public static PriorityQueue<Node> queue = new PriorityQueue<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
V = Integer.parseInt(br.readLine());
table = new int[N + 1];
Arrays.fill(table, Integer.MAX_VALUE);
adjacentList = new ArrayList[N + 1];
visited = new boolean[N + 1];
for (int i = 0; i <= N; i++) {
adjacentList[i] = new ArrayList<>();
}
for (int t = 0; t < V; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
adjacentList[u].add(new Node(v, w));
}
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
table[start] = 0;
System.out.println(dijkstra(start, end));
}
public static int dijkstra(int start, int end) {
queue.offer(new Node(start, 0));
while (!queue.isEmpty()) {
Node curNode = queue.poll();
if(set.contains(curNode.num)){
continue;
}
set.add(curNode.num);
for (Node childNode : adjacentList[curNode.num]) {
if (table[childNode.num] > table[curNode.num] + childNode.weight) {
table[childNode.num] = table[curNode.num] + childNode.weight;
queue.add(new Node(childNode.num, table[childNode.num]));
}
}
}
return table[end];
}
}
class Node implements Comparable<Node> {
int num;
int weight;
public Node(int num, int weight) {
this.num = num;
this.weight = weight;
}
public Node() {
}
@Override
public String toString() {
return "[" + num + ", " + weight + "]";
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
}
한노드를 방문했는지 확인하는 HashSet이 필요하다.
다익스트라 알고리즘상 O(V^2)이되게 로직을 구현해야한다.
로직을 조금 실수하면 space complexity나 time complexity를 초과하기때문에 조심해야한다.
특히 set을 언제추가하고 continue해야할지가 그 과정의 핵심이다.
'PS > 다익스트라' 카테고리의 다른 글
[JAVA] 백준 1753 - 최단경로 (0) | 2024.04.09 |
---|---|
[JAVA] 백준 1504 - 특정한 최단 경로 (0) | 2024.04.08 |