[Leetcode] 743. Network Delay Time

[uijin-j]

문제 링크

[ASak1104]

743. Network Delay Time

• 언어 : Java, Kotlin
• 코드 : 깃허브
• 성능
  • Java (Floyd-Warshall) : Time: 13 ms (76.94%), Space: 49.9 MB (5.36%)
  • Kotlin (Dijkastra) : Time: 319 ms (82.02%), Space: 48 MB (73.03%)

Java 풀이

```java import java.util.Arrays; class Solution { static final int MAX = (int) 1e9; static int[][] dists; public int networkDelayTime(int[][] times, int n, int k) { dists = new int[n + 1][n + 1]; for (int u = 1; u <= n; u++) { Arrays.fill(dists[u], MAX); dists[u][0] = 0; dists[u][u] = 0; } for (int[] time : times) { dists[time[0]][time[1]] = time[2]; } floydWarshall(n); return getDelayTime(k); } void floydWarshall(int n) { for (int k = 1; k <= n; k++) { for (int u = 1; u <= n; u++) { for (int v = 1; v <= n; v++) { dists[u][v] = Math.min(dists[u][v], dists[u][k] + dists[k][v]); } } } } int getDelayTime(int k) { int max = -1; for (int w : dists[k]) { if (w == MAX) { return -1; } max = Math.max(max, w); } return max; } } ```

Kotlin 풀이

```kt import java.util.* const val MAX = 1e9.toInt() class Solution { lateinit var edges: Array> fun networkDelayTime(times: Array, n: Int, k: Int): Int { edges = Array(n) { arrayListOf() } for ((u, v, w) in times) { edges[u - 1] += Edge(v - 1, w) } return dijkstra(k - 1) } fun dijkstra(start: Int): Int { val dists: Array = Array(edges.size) { MAX } val pq = PriorityQueue(compareBy(Edge::w)) pq += Edge(start, 0) dists[start] = 0 while (pq.isNotEmpty()) { val (u, cost) = pq.poll() if (cost > dists[u]) { continue } for ((v, w) in edges[u]) { if (dists[v] <= cost + w) { continue } pq += Edge(v, cost + w) dists[v] = cost + w } } if (MAX in dists) { return -1 } return dists.max() } data class Edge(val node: Int, val w: Int) } ```

코멘트

• 가장 기본적인 유형의 Shortest Path 문제네요
• 저는 Floyd-Warshall, Dijkstra 두 방식으로 풀어봤습니다
• 해당 문제에서 k를 시작점으로 하는 경로만 필요하기 때문에 Floyd-Warshall은 무겁지 않을까? 할 수 있지만
• 구현하기 쉽기 때문에 저는 자주 사용하는 것 같습니다
  • 문제에서 주어지는 n의 값이 작기도 하고요!

[yenzip]

743. Network Delay Time

• 언어: C++
• 성능: Time: 81ms (94.49%), Memory: 43.9MB (44.77%)

C++ 코드 풀이

```c++ class Solution { public: vector>> graph; vector dist; void dijkstra(int s) { priority_queue> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { int now = pq.top().second; int weight = -pq.top().first; pq.pop(); if (dist[now] < weight) { continue; } for (auto next : graph[now]) { int cost = weight + next.second; if (cost < dist[next.first]) { dist[next.first] = cost; pq.push({-cost, next.first}); } } } } int networkDelayTime(vector>& times, int n, int k) { int answer = 0; graph.resize(n + 1); dist.resize(n + 1, INT_MAX); for (auto time : times) { graph[time[0]].push_back({time[1], time[2]}); } dijkstra(k); for (int i = 1; i <= n; i++) { answer = max(answer, dist[i]); } return answer == INT_MAX ? -1 : answer; } }; ```

코멘트

• 최단 거리 문제로, 간선이 모두 양수이므로 다익스트라 알고리즘을 활용하여 문제를 해결했습니다.
• JAVA로도 다시 풀어서 올리겠습니당..!

[uijin-j]

743. Network Delay Time

• Language : Java
• 성능 🌟 시간: 6 ms, 메모리: 49.04MB 🌟

코드 풀이

```java class Solution { private final int INF = 987654321; private class Node { int to, time; Node(int to, int time) { this.to = to; this.time = time; } } public int networkDelayTime(int[][] times, int n, int k) { int[][] dist = new int[n+1][n+1]; int[] min = new int[n+1]; boolean[] check = new boolean[n+1]; for (int i = 0; i <= n; i++) Arrays.fill(dist[i], INF); Arrays.fill(min, INF); min[k] = 0; for(int[] time: times) { int u = time[0]; int v = time[1]; int t = time[2]; dist[u][v] = t; } Queue pq = new PriorityQueue<>((a, b) -> a.time - b.time); pq.add(new Node(k, 0)); while(!pq.isEmpty()) { Node node = pq.poll(); if(check[node.to]) continue; check[node.to] = true; // 최단거리 확정 for(int i = 1; i <= n; ++i) { if(dist[node.to][i] == INF) continue; if(min[node.to] + dist[node.to][i] < min[i]) { min[i] = min[node.to] + dist[node.to][i]; pq.offer(new Node(i, min[i])); } } } int max = 0; for(int i = 1; i <= n; ++i) { max = Math.max(min[i], max); } return max == INF ? -1 : max; } } ```

코멘트

• 기본적인 다익스트라 알고리즘 문제였습니다!
• 그렇지만 오랜만에 푸니.. 풀이법이 조금 헷갈리더라구요ㅜ 특히 if(check[node.to]) continue;문을 처음에는 while문 안에 있는 for문에 넣어줬다가 답이 나오지 않아서 다시 보니 밖으로 빼내야 했었습니당..

[shoeone96]

743. Network Delay Time

• Language : Java
• 성능

코드 풀이

```java class Solution { static class Edge{ int to; int weight; public Edge(int to, int weight){ this.to = to; this.weight = weight; } } static class Info{ int to; int distance; public Info(int to, int distance){ this.to = to; this.distance = distance; } } public int networkDelayTime(int[][] times, int n, int k) { List [] edges = new ArrayList [n+1]; int[] distance = new int[n + 1]; for(int i = 1; i <= n; i++){ distance[i] = Integer.MAX_VALUE; } for(int i = 1; i <=n; i++){ edges[i] = new ArrayList<>(); } for(int i = 0; i < times.length; i++){ int from = times[i][0]; int to = times[i][1]; int weight = times[i][2]; edges[from].add(new Edge(to, weight)); } PriorityQueue infos = new PriorityQueue<>(Comparator.comparing(info -> info.distance)); infos.add(new Info(k, 0)); distance[k] = 0; while(!infos.isEmpty()){ Info info = infos.poll(); if(info.distance != distance[info.to]) continue; for(Edge e : edges[info.to]){ if(distance[info.to] + e.weight >= distance[e.to]) continue; distance[e.to] = distance[info.to] + e.weight; infos.add(new Info(e.to, distance[e.to])); } } int answer = 0; for(int i = 1; i <=n; i++){ if(distance[i] == Integer.MAX_VALUE) return -1; if(answer < distance[i]) answer = distance[i]; } return answer; } } ```

코멘트

• 다익스트라... 풀어봤읍니다...

[Sehee-Lee-01]

743. Network Delay Time

• Language : Java

코드 풀이

```java class Solution { static class Edge { int num; int dis; Edge(int num, int dis) { this.num = num; this.dis = dis; } } public int networkDelayTime(int[][] times, int n, int k) { int[] dis = new int[n + 1]; List[] edges = new ArrayList[n + 1]; for (int i = 1; i <= n; i++) { dis[i] = -1; edges[i] = new ArrayList<>(); } for (int[] time : times) { edges[time[0]].add(new Edge(time[1], time[2])); } PriorityQueue pq = new PriorityQueue<>((a, b) -> a.dis - b.dis); pq.add(new Edge(k, 0)); dis[k] = 0; while (!pq.isEmpty()) { Edge curr = pq.poll(); for (Edge edge : edges[curr.num]) { if (dis[edge.num] == -1 || (dis[edge.num] > dis[curr.num] + edge.dis)) { dis[edge.num] = dis[curr.num] + edge.dis; pq.add(edge); } } } int res = 0; boolean isImpossible = false; for (int minDis : dis) { if (minDis == -1) { isImpossible = true; break; } if (minDis > res) res = minDis; } return isImpossible ? -1 : res; } } ```

코멘트

• pq로 푸니 속도가 빠르긴 하네용!
• 이번 주 스터디장 야무진님 덕분에 오랜만에 개념 복습하고 푸니 더 잘 풀리네용!👍

[IjjS]

743. Network Delay Time

• 언어: 자바
• 성능: 37ms (12.46%), 47.5MB (61.73%)

코드 풀이

```java // 코드 작성 class Solution { public int networkDelayTime(int[][] times, int n, int k) { Map> graph = new HashMap<>(); for (int[] time : times) { graph.putIfAbsent(time[0], new HashMap<>()); graph.get(time[0]).put(time[1], time[2]); } Queue pq = new PriorityQueue<>((arr1, arr2) -> arr1[1] - arr2[1]); pq.add(new int[] {k, 0}); Map dist = new HashMap<>(); while (!pq.isEmpty()) { int[] curr = pq.poll(); int node = curr[0]; int cost = curr[1]; if (!dist.containsKey(node)) { dist.put(node, cost); if (graph.containsKey(node)) { for (int next : graph.get(node).keySet()) { int alt = cost + graph.get(node).get(next); pq.add(new int[] {next, alt}); } } } } if (dist.size() == n) { return Collections.max(dist.values()); } return -1; } } ```

코멘트