[백준] 1504번 : 특정한 최단 경로

문제

https://www.acmicpc.net/problem/1504

풀이

[백준] 1504 : 특정한 최단 경로 🥇(골드 4)
🎯 24.579%
⏰ 걸린 시간 : 110분
⏲ 시간복잡도
: 다익스트라 -> O(ElogV) : EV인데 우선순위 큐 사용해주면 탐색이 logV로 줄어든다.

• 알고리즘 유형 : [다익스트라]

✅ 문제 요약

0. 첫째 줄에 정점의 개수 N과 간선의 개수 E가
1. 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다.
2. 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다.
3. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

✅ 출력

• 첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

💡 주의할점
이경우 생길 수 있는 경로는 2가지 이다.

• 시작정점 -> stop1 -> stop2 -> 도착정점
• 시작정점 -> stop2 -> stop1 -> 도착정점

✅ 풀이방법 & 다익스트라 알고리즘로 푼 이유?

✔️ 전형적인 최단 경로 문제이다.
0. 다익스트라 : 한 정점에서 모든 정점까지의 거리를 계산함
1. 가는 길을 택하는데 최소의 거리 길이를 택하여서 가야하기 때문이다.
2. 플로이드 워셜의 경우는 시간 복잡도가 O(V^3)인데 D의 입력이 10,000이기 때문에 2초를 초과 할 수 있다.

코드(code)

import sys
import heapq
input = sys.stdin.readline

N ,E =map(int, input().split())
INF = int(1e9)
graph = [[] for _ in range(N+1)]

for i in range(E):
    s, e, l = map(int, input().split())
    graph[s].append((e,l))
    graph[e].append((s,l))
v1,v2 = map(int, input().split())

def dijkstra(start,end):
    path = [INF]*(N+1)
    q = []
    heapq.heappush(q,(0,start))
    path[start]=0

    while q:
        length, now = heapq.heappop(q)
        if path[now] < length:
            continue
       
        for e,l in graph[now]:
            now_length = l + length
            if now_length < path[e]:
                path[e] = now_length
                heapq.heappush(q,(now_length,e))
    return path[end]


# 🔥 주의사항 볼 것
path1 = dijkstra(1,v1) +dijkstra(v1,v2) +dijkstra(v2,N)
path2 = dijkstra(1,v2) +dijkstra(v2,v1) +dijkstra(v1,N)
if path1 >= INF and path2 >= INF:
    print(-1)
else:
    print(min(path1,path2))

회고

조금씩 이해가 되면서 풀린다.
😼 다익스트라 알고리즘 연습 또 연습!!

• 가중치가 있는 최단거리를 찾는 알고리즘으로는 다익스트라가 적합하다.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/Dijkstra/1504(%ED%8A%B9%EC%A0%95%ED%95%9C%20%EC%B5%9C%EB%8B%A8%20%EA%B2%BD%EB%A1%9C).py