[백준] 최소 비용 구하기

[uijin-j]

문제 링크

[ASak1104]

1916. 최소비용 구하기

• 언어 : Java
• 코드 : 깃허브
• 성능 : Time: 464 ms, Memory: 77912 KB

Java 풀이

```java import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; class Main { static final int INF = (int) 1e9; static StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in)); static List[] edges; static int[][] buses; static int n, m; public static int readInt() throws IOException { st.nextToken(); return (int) st.nval; } public static void main(String[] args) throws IOException { n = readInt(); m = readInt(); buses = new int[n][n]; edges = new List[n]; for (int u = 0; u < n; u++) { Arrays.fill(buses[u], INF); edges[u] = new ArrayList<>(); } for (int i = 0; i < m; i++) { int u = readInt() - 1; int v = readInt() - 1; int w = readInt(); buses[u][v] = Math.min(buses[u][v], w); } for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { if (buses[u][v] == INF) { continue; } edges[u].add(v); } } int src = readInt() - 1; int dst = readInt() - 1; System.out.println(dijkstra(src, dst)); } private static int dijkstra(int src, int dst) { int[] dists = new int[n]; PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); Arrays.fill(dists, INF); dists[src] = 0; pq.add(new int[]{src, 0}); while (!pq.isEmpty()) { int u = pq.peek()[0]; int cost = pq.poll()[1]; if (u == dst) { return cost; } for (int v : edges[u]) { int newDist = cost + buses[u][v]; if (dists[v] <= newDist) { continue; } dists[v] = newDist; pq.add(new int[]{v, newDist}); } } return dists[dst]; } } ```

코멘트

• 이름에 충실한 문제네요
• 처음에 시간초과가 나서 뭐가 문제지? 했는데
• 동일한 경로, 다른 비용의 버스를 고려하는 것이 중요했던 것 같아요
• 문제에서 필요한 정보를 구하는 순간 계산을 중단하는 최적화가 필요한 문제였던 것 같습니다!

[shoeone96]

1916. 최소비용 구하기

• 언어 : Java
• 성능 : Time: 568 ms, Memory: 56368 KB

Java 풀이

```java import java.io.*; import java.util.*; public class Main { static int N; static int M; static List[] edges; static int start; static int destination; static int[] distances; static class Edge { int end; int price; public Edge(int end, int price) { this.end = end; this.price = price; } } static class Info{ int end; int distance; public Info(int end, int distance){ this.end = end; this.distance = distance; } } public static void main(String[] args) throws IOException { input(); dijkstra(start); System.out.println(distances[destination]); } private static void dijkstra(int start) { for(int i = 1; i <= N; i++){ distances[i] = Integer.MAX_VALUE; } distances[start] = 0; PriorityQueue infos = new PriorityQueue<>(Comparator.comparing(info -> info.distance)); infos.add(new Info(start, 0)); while(!infos.isEmpty()){ Info info = infos.poll(); if(info.distance != distances[info.end]) continue; for(Edge edge : edges[info.end]){ if (distances[info.end] + edge.price >= distances[edge.end]) continue; distances[edge.end] = info.distance + edge.price; infos.add(new Info(edge.end, distances[edge.end])); } } } private static void input() throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); N = Integer.parseInt(st.nextToken()); st = new StringTokenizer(bf.readLine()); M = Integer.parseInt(st.nextToken()); distances = new int[N + 1]; edges = new ArrayList[N + 1]; for(int i = 1; i <=N; i++){ edges[i] = new ArrayList<>(); } for(int i = 0; i

코멘트

• 이 문제 다익스트라 문제로 연습한 다음에 네트워크 풀었어용
• 한번 해보니까 재밌기도 한데 좀 더 연습이 필요할 것 같네용 :)

[uijin-j]

1916. 최소 비용 구하기

• Language : Java
• 성능 🌟 시간: 432 ms, 메모리: 50508 KB 🌟

코드 풀이

```java import java.io.*; import java.util.*; public class Main { static class Node { int city, cost; Node(int city, int cost) { this.city = city; this.cost = cost; } } public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(bf.readLine()); int m = Integer.parseInt(bf.readLine()); List[] buses = new ArrayList[n+1]; for(int i = 1; i <= n; ++i) buses[i] = new ArrayList<>(); for(int i = 0; i < m; ++i) { StringTokenizer st = new StringTokenizer(bf.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); buses[from].add(new Node(to, cost)); } StringTokenizer st = new StringTokenizer(bf.readLine()); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); int[] dist = new int[n+1]; Arrays.fill(dist, Integer.MAX_VALUE); PriorityQueue pq = new PriorityQueue<>((a, b) -> a.cost - b.cost); pq.offer(new Node(start, 0)); dist[start] = 0; while(!pq.isEmpty()) { Node node = pq.poll(); int now = node.city; int cost = node.cost; if(dist[now] < cost) continue; if(now == end) { System.out.println(dist[end]); return; } dist[now] = cost; for(Node next : buses[now]) { if(dist[next.city] > dist[now] + next.cost) { dist[next.city] = dist[now] + next.cost; pq.offer(new Node(next.city, dist[next.city])); } } } } } ```

코멘트

• 다익스트라 알고리즘 정석 문제
• 저번 주 다른 분들의 풀이법을 듣고, chech[] 배열 대신 dist[] 값을 확인한 뒤 continue해 주었습니당!

[Sehee-Lee-01]

1916. 최소 비용 구하기

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; public class Main { static class Edge { int num; int weight; Edge(int num, int weight) { this.num = num; this.weight = weight; } } static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static List[] edges; static int[] weights; static int N, M, start, end; public static void main(String[] args) throws IOException { N = Integer.parseInt(br.readLine()); edges = new ArrayList[N + 1]; weights = new int[N + 1]; for (int i = 1; i <= N; i++) { edges[i] = new ArrayList<>(); weights[i] = Integer.MAX_VALUE; } M = Integer.parseInt(br.readLine()); for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int s = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); edges[s].add(new Edge(e, w)); } st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken()); end = Integer.parseInt(st.nextToken()); System.out.println(daikstra()); } static long daikstra() { PriorityQueue pq = new PriorityQueue<>((a, b) -> a.weight - b.weight); pq.add(new Edge(start, 0)); while (!pq.isEmpty()) { Edge curr = pq.poll(); if (weights[curr.num] <= curr.weight) continue; weights[curr.num] = curr.weight; if (curr.num == end) { return weights[end]; } for (Edge e : edges[curr.num]) { if (weights[e.num] > weights[curr.num] + e.weight) { pq.add(new Edge(e.num, weights[curr.num] + e.weight)); } } } return weights[end]; } } ```

코멘트

• 다익스트라 기본 문제
• dfs/bfs와 로직이 조금 비슷한데 시간 초과가 나는 지점을 잘 관리해줘야하는 것 같습니다!

[yenzip]

1916. 최소 비용 구하기

• Language : C++

코드 풀이

```c++ #include using namespace std; int N, M; vector>> graph; vector D; void dijkstra(int s) { priority_queue> pq; D[s] = 0; pq.push({ 0, s }); while (!pq.empty()) { int now = pq.top().second; int dist = -pq.top().first; pq.pop(); if (D[now] < dist) { continue; } for (auto next : graph[now]) { int cost = dist + next.second; if (cost < D[next.first]) { D[next.first] = cost; pq.push({ -cost, next.first }); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M; graph.resize(N + 1); D.resize(N + 1, INT_MAX); for (int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({ v, w }); } int s, e; cin >> s >> e; dijkstra(s); cout << D[e]; return 0; } ```

Comment

• 시간이 없어 C++로 푼 다익스트라 문제입니다. 다음에 복습할 때, JAVA로 풀어보겠습니다..!