📝오늘 공부한 것
- 프로그래머스 문제풀기
- 스파르타코딩클럽 자료구조 & 알고리즘 5주차 강의 듣기
- 이력서 수정하기
알게 된 점❗
[ 다익스트라 알고리즘 ]
1. 출발지를 s로 정하고, 다음과 같이 표시한다.
(s, t, x, y, z 순)
거리 = [0, inf, inf, inf, inf]
방문 = [True, False, False, False, False]
2. 갈 수 있는 노드들의 최소거리를 측정한다.
s->t: 10
s->y: 5
(s, t, x, y, z 순)
거리 = [0, 10, inf, 5, inf]
방문 = [True, False, False, False, False]
3. 방문 안한 녀석들 중 가장 가까운 녀석인 y를 방문하고, 최소거리를 측정한다.
y->t: 3
y->x: 9
y->z: 2
(s, t, x, y, z 순)
거리 = [0, 8, 14, 5, 7]
방문 = [True, False, False, True, False]
4. 방문 안한 녀석들 중 가장 가까운 녀석인 z를 방문하고, 최소거리를 측정한다.
z->x: 6
(s, t, x, y, z 순)
거리 = [0, 8, 13, 5, 7]
방문 = [True, False, False, True, True]
5. 방문 안한 녀석들 중 가장 가까운 녀석인 t를 방문하고, 최소거리를 측정한다.
t->x: 1
t->y: 2
(s, t, x, y, z 순)
거리 = [0, 8, 9, 5, 7]
방문 = [True, True, False, True, True]
6. 방문 안한 녀석들 중 가장 가까운 녀석인 x를 방문하고, 최소거리를 측정한다.
x->z: 4
(s, t, x, y, z 순)
거리 = [0, 8, 9, 5, 7]
방문 = [True, True, True, True, True]
7. 방문 안한 노드가 없으므로 끝낸다.
(s, t, x, y, z 순)
거리 = [0, 8, 9, 5, 7]
방문 = [True, True, True, True, True]
[ 다익스트라 구현]
다익스트라 구현(1)
import sys
from min_cost.dijkstra import dijkstra_naive, dijkstra_pq
with open('testcase1.txt') as f:
sys.stdin = f
input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
assert dijkstra_naive(graph, start) == [1000000000, 0, 2, 3, 1, 2, 4]
INF = int(1e9)
def dijkstra_naive(graph, start):
def get_smallest_node():
min_value = INF
idx = 0
for i in range(1, N):
if dist[i] < min_value and not visited[i]:
min_value = dist[i]
idx = i
return idx
N = len(graph)
visited = [False] * N
dist = [INF] * N
visited[start] = True
dist[start] = 0
for adj, d in graph[start]:
dist[adj] = d
# N개의 노드 중 첫 노드는 이미 방문했으므로,
# N-1번 수행하면 된다.
for _ in range(N - 1):
# 가장 가깝고 방문 안한 녀석을 고르고,
cur = get_smallest_node()
visited[cur] = True
# 최단거리를 비교, 수정한다.
for adj, d in graph[cur]:
cost = dist[cur] + d
if cost < dist[adj]:
dist[adj] = cost
return dist
다익스트라 구현(2)
import heapq
def dijkstra_pq(graph, start):
N = len(graph)
dist = [INF] * N
q = []
# 튜플일 경우 0번째 요소 기준으로 최소 힙 구조.
# 첫 번째 방문 누적 비용은 0이다.
heapq.heappush(q, (0, start))
dist[start] = 0
while q:
# 누적 비용이 가장 작은 녀석을 꺼낸다.
acc, cur = heapq.heappop(q)
# 이미 답이 될 가망이 없다.
if dist[cur] < acc:
continue
# 인접 노드를 차례대로 살펴보며 거리를 업데이트한다.
for adj, d in graph[cur]:
cost = acc + d
if cost < dist[adj]:
dist[adj] = cost
heapq.heappush(q, (cost, adj))
return dist
import sys
from min_cost.dijkstra import dijkstra_naive, dijkstra_pq
with open('testcase1.txt') as f:
sys.stdin = f
input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
assert dijkstra_naive(graph, start) == [1000000000, 0, 2, 3, 1, 2, 4]
assert dijkstra_pq(graph, start) == [1000000000, 0, 2, 3, 1, 2, 4]
시간복잡도 비교
- Naive: 이중 for 문이므로 O(V^2)
- PriorityQueue: O(ElogV)
[ 최단경로와 플로이드 - 워셜 ]
- 다익스트라 : 출발점을 정했을 때 다른 노드에 이르는 최단거리
- 플로이드-워셜 : 모든 지점에서 다른 모든 지점까지 최단거리
- 자기자신으로 가는 비용은 0
- 직접 연결되어있지 않은 경로는 무한대.
import sys
from collections import defaultdict
from pprint import pprint
from min_cost.floyd_warshall import floyd_warshall
with open('testcase_fw.txt') as f:
sys.stdin = f
input = sys.stdin.readline
N = int(input())
M = int(input())
graph = defaultdict(list)
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append((b, c))
pprint(floyd_warshall(graph))
INF = int(1e9)
def floyd_warshall(graph):
N = len(graph)
dist = [[INF] * (N + 1) for _ in range(N + 1)]
for idx in range(1, N + 1):
dist[idx][idx] = 0
for start, adjs in graph.items():
for adj, d in adjs:
dist[start][adj] = d
for k in range(1, N + 1):
for a in range(1, N + 1):
for b in range(1, N + 1):
dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])
return dist
'TIL(Today I Learned)' 카테고리의 다른 글
TIL-231011(TDD) (0) | 2023.10.11 |
---|---|
TIL-231010(자료구조 & 알고리즘 5주차) (0) | 2023.10.10 |
TIL-231007(자료구조 & 알고리즘 4주차) (0) | 2023.10.07 |
TIL-231006(자료구조 & 알고리즘 4주차) (0) | 2023.10.06 |
TIL-231005(자료구조 & 알고리즘 3주차) (0) | 2023.10.06 |