항해99, 5주차 네트워크 딜레이 타임

Today I learned
2022/02/07

회고록

2/07

항해 99, 알고리즘 4주차(항해 5주차)

교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)

최단경로

1. 이론

이론 정리 포스팅 글(내 벨로그)

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

2. 문제

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

https://leetcode.com/problems/network-delay-time/

3. MySol

• Dijkstra Algorithm

import sys


def dijkstra(times, start, n):

    graph = [None]*(n+1)

    for i in times:
        if graph[i[0]] is None:
            graph[i[0]] = [[i[1],i[2]]]
        else:
            graph[i[0]].append([i[1],i[2]])


    visited = [False]*(n+1)
    distance = [INF]*(n+1)

    def get_nearest():
        idx = 0
        min = INF
        for i in range(len(distance)):
            if visited[i] is False and min > distance[i]:
                min = distance[i]
                idx = i

        return idx


    def algo():

        distance[start] = 0

        for _ in range(n):

            now = get_nearest()
            visited[now] = True

            if graph[now] is None:
                continue

            for dest_dist in graph[now]:
                cost = distance[now] + dest_dist[1]

                if distance[dest_dist[0]] > cost:
                    distance[dest_dist[0]] = cost


    algo()

    distance.pop(0)

    result = max(distance)

    print(f'{result}')

    return distance


if __name__ == '__main__':

    INF = int(1e9)

    n = 4
    k = 2

    times = [
        [2,1,1],
        [2,3,1],
        [3,4,1]
    ]

    result = dijkstra(times, k, n)
    print(f'{result}')

4. 배운 점

• 다익스트라 알고리즘을 구현하여 문제를 해결하였다.

5. 총평

다익스트라 알고리즘 익히기