Network Delay Time
내 풀이
처음에 문제를 잘못 이해했다. n이 도착지점이고 k가 출발지점일 때, n에서 k까지 가는 최단경로를 구하는 문제인줄 알았다.
times = [[2,1,1],[2,3,1]]그래서 위와 같은 예제에서 2 -> 1 -> 2로 가는것을 기존 알고리즘에서 visited까지 사용해가며 구했지만 틀린 답이 나왔고 다시 문제를 이해했다.
제대로 이해한 문제는 k에서 출발해서 전파할 때 걸리는 최단 시간을 구하는 문제였다.
import heapq
class Solution:
def dijkstra(self, graph, start) :
costs = {}
dp = {}
pq = []
heapq.heappush(pq, [0, start, 0])
while pq :
cur_cost, cur_v, cur_depth = heapq.heappop(pq)
if cur_v not in costs :
costs[cur_v] = cur_cost
if cur_depth not in dp :
dp[cur_depth] = cur_cost
else :
dp[cur_depth] = min(dp[cur_depth], cur_cost)
next_depth = cur_depth + 1
for next_cost, next_v in graph[cur_v] :
next_cost = cur_cost + next_cost
heapq.heappush(pq,[next_cost, next_v, next_depth])
max_key = max(dp.keys())
return dp[max_key]
def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
graph = [[] for _ in range(n + 1)]
for time in times :
a, b, c = time
graph[a].append([c, b])
ans = -1
try :
ans = self.dijkstra(graph, k)
except Exception as err :
print(f'alert exception : {err}')
if(ans == 0) :
ans = -1
return ans위와 같이 제출하고 최종적으로 실패하고 다른 사람의 풀이를 보았다.
내가 일으킨 오류
- 전체 노드를 전파했는가?
- 문제를 제대로 이해못한게 원인이 되었다. n이 대체 왜 필요하지? 라고 생각하고 있었는데 1~n까지의 vertax(간선)이 들어온다는 것을 알았다.
- 즉, 발생한 costs에 n개의 노드가 들어있어야 한다. n개의 노드가 모두 costs에 들어있는지 확인하면 되는 문제였다.
- 모든 노드를 방문할 때 걸린 최소 비용은 어떻게 되는가?
- 다익스트라 알고리즘에 대한 이해 부족이 원인이었던 것 같다.
- 다익스트라 알고리즘은 모든 경로를 방문하는 알고리즘이고 다익스트라 알고리즘을 통해서 발생한 비용의 최대값은 모든 노드를 방문하는데 필요한 최대값이다.
정답
import heapq
class Solution:
def dijkstra(self, graph, start, n):
costs = {}
pq = []
heapq.heappush(pq, [0, start])
while pq:
cur_cost, cur_v = heapq.heappop(pq)
if cur_v not in costs:
costs[cur_v] = cur_cost
for next_cost, next_v in graph[cur_v]:
next_cost = cur_cost + next_cost
heapq.heappush(pq, [next_cost, next_v])
ans = max(costs.values())
for i in range(1, n + 1):
if i not in costs:
ans = -1
return ans
def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
graph = [[] for _ in range(n + 1)]
for time in times:
a, b, c = time
graph[a].append([c, b])
ans = self.dijkstra(graph, k, n)
return ans고민의 흔적들
