심화 과정 14 일차

1. 자료구조 및 알고리즘 14일차 수강하기

 

 -  다익스트라

 

 - 플로이드 - 워셜

 

2. 새롭게 알게된 지식

 - 최단 경로 알고리즘 : 다익스트라

  경로의 가중치가 음수가 아니고 시작점이 주어진 경우 최단 경로를 찾는 알고리즘

 

 

 

 

과제 1 : 네트워크 딜레이 타임 : https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

 

- 접근 : 

 

 다익스트라 알고리즘 적용

 

 - 코드 구현 : 

 

import heapq

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        start = k
        edges = [[] for _ in range(n+1)]

        for i in range(len(times)):
            cur, adj, weight = times[i]
            edges[cur].append((adj, weight))
        
        #나올 수 없는 최대 거리 = (간선 수 + 1) * 최대 가중치
        max_weight = 100 * len(times)

        dist_arr = [max_weight] * (n + 1)
        dist_arr[start] = 0

        queue = []
        heapq.heappush(queue, (0, start))

        while queue:
            dist_cur, cur = heapq.heappop(queue)

            # 현재까지 도달 했을 때, 그 값이 이전에 온 경로 보다 긴 경우
            if dist_arr[cur] < dist_cur:
                continue

            # 연결된 간선에 거리에 대한 정보를 업데이트
            for adj, weight in edges[cur]:
                # 인접한 노드에 갈 수 있는 더 짧은 거리를 찾았다면 이에 대한 정보를 갱신하고 큐에 추가
                if dist_arr[adj] > dist_arr[cur] + weight:
                    dist_arr[adj] = dist_arr[cur] + weight
                    heapq.heappush(queue, (dist_arr[adj], adj))
        # 최소 거리 값
        res = 0

        for i in range(1, n + 1):
            if dist_arr[i] == max_weight:
                return -1
            
            #가장 큰 값이 끝까지 도달한 경우
            res = max(res, dist_arr[i])
        return res

 

 

과제 2 : 최단경로 https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

- 접근 : 

 

 다익스트라 알고리즘 적용

 

 - 코드 구현 : 

 

import sys
import heapq

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write

    def answer(self):
        v, e = map(int, self.input().split())
        k = int(self.input())
        edges = [[] for _ in range(v+1)]
        
        max_dist = 10*e + 1
        dist_arr = [max_dist] * (v+1)
        dist_arr[k] = 0

        for _ in range(e):
            cur, adj, weight = map(int, self.input().split())
            edges[cur].append((adj, weight))

        queue = []
        heapq.heappush(queue, (0, k))

        while queue:
            dis_cur, cur = heapq.heappop(queue)
            
            if dis_cur > dist_arr[cur]:
                continue

            for adj, weight in edges[cur]:
                temp = dis_cur + weight
                if dist_arr[adj] > temp:
                    dist_arr[adj] = temp
                    heapq.heappush(queue, (temp, adj))

        for i in range(1, v+1):
            res = 'INF' if dist_arr[i] == max_dist else str(dist_arr[i])
            self.output(f'{res}\n')

s = Solution()
s.answer()

 

 

\