[백준] 1446번 : 지름길

문제

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

풀이

[백준] 1446 : 지름길 🥈(실버1)
🎯 53.420%
⏰ 걸린 시간 :시간초과
⏲ 시간복잡도
: 다익스트라 -> O(ElogV) : EV인데 우선순위 큐 사용해주면 탐색이 logV로 줄어든다.

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

✅ 문제 요약

0. 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다.
1. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다.
2. 세준이는 지름길을 이용해 운전해야하는 거리의 최솟값을 출력하시오.
3. 단, 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

✅ 출력

• 세준이가 운전해야하는 거리의 최솟값을 출력하시오.

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

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

코드(code)

import heapq # 우선순위 큐 라이브러리 O(logN)
import sys
input = sys.stdin.readline

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

# N:지름길의 개수, D:고속도로 길이
N, D = map(int,input().split())
graph = [[] for _ in range(D+1)]
# 최단 거리를 일단 무한으로 초기화
distance = [INF] * (D+1)
# 일단 거리를 1로 초기화
for i in range(D):
    graph[i].append((i+1, 1))

# 지름길이 있으면 업데이트
for _ in range(N):
    start, end, length = map(int,input().split())
    if end > D : #만일 고속도로 길이보다 end값이 크면 무시
        continue
    graph[start].append((end,length))
    # start에 end와 length값 넣어주기

# 다익스트라 정의    >>
def dijkstra(start):
    Que=[]
    heapq.heappush(Que,(0,start))  #start노드로 가기 위한 최단경로를 0으로 설정하여 큐에 삽입
    distance[start]=0
    while Que:
        dist, now = heapq.heappop(Que)  # dist는 여태까지 거리

        if dist > distance[now]:
            continue
        for i in graph[now]:
            now_dist= dist +i[1]
            if now_dist < distance[i[0]]:  # 현재거리 < end값 (즉, 지름길을 택했을 때가 더 짧은 경우)
                distance[i[0]] = now_dist # 거리를 지름길로 대체함
                heapq.heappush(Que,(now_dist, i[0])) #(현재까지거리, 현재시점)



# print(graph)

dijkstra(0)
print(distance[D])

회고

처음풀어보는 다익스트라 알고리즘이라 까다로웠다..
다익스트라 알고리즘 익숙해지도록 해야겠다.

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

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/Dijkstra/1446(%EC%A7%80%EB%A6%84%EA%B8%B8).py