Page tree

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Code Block
languagepy
titlenetwork_delay_time완전탐색 : 8464 ms
linenumberstrue
class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = {}
        for i in range(1, N + 1):
            graph.setdefault(i, [])
        for node in times:
            graph[node[0]].append([node[1], node[2]])
            
        dist = {node: float('inf') for node in range(1, N + 1)}

        def dfs(node, depth):
            if depth >= dist[node]:
                return
            dist[node] = depth
            for n, w in graph[node]:
                dfs(n, depth + w)

        dfs(K, 0)
        ans = max(dist.values())
        return ans if ans < float('inf') else -1
Code Block
languagepy
title다익스트라 : 452ms
linenumberstrue
class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = collections.defaultdict(dict)
        for i in range(1, N + 1):
            graph[i] = {}

        for v, n, w in times:
            graph[v][n] = w

        infinity = float("inf")
        costs = {}
        for e in graph:
            if e not in costs:
                if e == K:
                    costs[e] = 0
                    for se in graph[e]:
                        costs[se] = graph[e][se]
                else:
                    costs[e] = infinity

        visited = []
        node = self.find_lowest_cost_node(costs, visited)
        while node is not None:
            cost = costs[node]
            neighbors = graph[node]
            for n in neighbors.keys():
                new_cost = cost + neighbors[n]
                if costs[n] > new_cost:
                    costs[n] = new_cost
            visited.append(node)
            node = self.find_lowest_cost_node(costs, visited)

        ans = max(costs.values())
        return ans if ans < float('inf') else -1

    def find_lowest_cost_node(self, costs, visited):
        lowest_cost = float("inf")
        lowest_cost_node = None
        for node in costs:
            cost = costs[node]
            if cost < lowest_cost and node not in visited:
                lowest_cost = cost
                lowest_cost_node = node
        return lowest_cost_node