1. 자료구조 및 알고리즘 14일차 수강하기
- 다익스트라
- 플로이드 - 워셜
2. 새롭게 알게된 지식
- 최단 경로 알고리즘 : 다익스트라
경로의 가중치가 음수가 아니고 시작점이 주어진 경우 최단 경로를 찾는 알고리즘
과제 1 : 네트워크 딜레이 타임 : https://leetcode.com/problems/network-delay-time/
Network Delay Time - LeetCode
Can you solve this real interview question? Network Delay Time - 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 tar
leetcode.com
- 접근 :
다익스트라 알고리즘 적용
- 코드 구현 :
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번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
- 접근 :
다익스트라 알고리즘 적용
- 코드 구현 :
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()
\
'개발일지' 카테고리의 다른 글
5주차 WIL (0) | 2024.03.03 |
---|---|
심화 과정 15 일차 (1) | 2024.02.27 |
4주차 WIL (0) | 2024.02.25 |
심화 과정 13 일차 (1) | 2024.02.24 |
심화 과정 12 일차 (0) | 2024.02.23 |