4주차 (07월 25일)
목표
- 알고리즘 < 최단경로 > 문제풀기 (백준 1753번, 백준 1504번)
회고
- 알고리즘 < 최단경로 > 문제 : 백준 1753번(“최단경로”) -> 난이도 : 골드5
해결 방법 : 가중치가 있고 방향이 있는 그래프에서 한 정점에서 다른 모든 정점까지 최단거리를 구할때는 다익스트라 알고리즘을 사용한다.(모든 정점 간의 최단거리를 구할 때는 플로이드워셜 알고리즘 사용)
코드일부
while queue:
w, cur = heapq.heappop(queue)
if w > distance[cur]:
continue
for weight, end in graph[cur]:
if w + weight < distance[end]:
distance[end] = w + weight
heapq.heappush(queue, (weight + w, end))
- 알고리즘 < 최단경로 > 문제 : 백준 1504번(“특정한 최단경로”) -> 난이도 : 골드4
해결 방법 : 시작점에서 다익스트라 사용, 거쳐가는 점 v1, v2에서 각각 다익스트라 사용해서 총 다익스트라를 3번 사용하여서 거쳐가는 최단거리를 구한다.
코드일부
def dijkstra(start, goal):
distance = [INF] * (N + 1)
queue = []
heapq.heappush(queue, (0, start))
distance[start] = 0
while queue:
w, cur = heapq.heappop(queue)
if w > distance[cur]:
continue
for weight, end in graph[cur]:
if w + weight < distance[end]:
distance[end] = w + weight
heapq.heappush(queue, (weight + w, end))
return distance[goal]
case1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
case2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)
if min(case1, case2) < INF:
print(min(case1, case2))
else:
print(-1)