프론트엔드 개발자 중규리 입니다 ദി ᷇ᵕ ᷆ ) 자세히보기

PS/문제풀이

백준 1446 지름길 Python

중규리 2024. 1. 17. 18:25

🐸 문제 정보

 

1446번: 지름길

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이

www.acmicpc.net

 

🤖 알고리즘

다익스트라

 

⏱️ 풀이 시간

30.05m

 

📝 풀이

최근에 공부한 최단거리 포스팅을 읽어보면 쉽게 풀 수 있는 문제였다.

모든 거리 지점을 노드라고 생각하고, 각 지점에서 다음 지점까지 가중치 1씩을 기본으로 설정했다.

그리고 지름길이 있는 부분에 간선을 추가하여 다익스트라를 돌리면 되는 문제였다.

 

 

최단 경로 찾기 with Python

🌊 최단 경로 찾기 알고리즘 🐸 이해하기 최단경로 찾기 알고리즘? 노드 간 가중치가 주어질 때, 시작 노드부터 모든 노드까지의 최소값을 구하는 알고리즘이다. 이해하는데에 큰 어려움은 없

99uulog.tistory.com

 

뭔가 뿌듯했다.. 나 이제 최단 경로 찾기 잘할수있숴

 

🧑‍💻 나의 답

# pypy3

import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize

n, d = list(map(int, input().rstrip().split()))
graph = [[(i + 1, 1)] if i < d else [] for i in range(d + 1)]
distance = [INF] * (d + 1)

for _ in range(n):
    u, v, m = list(map(int, input().rstrip().split()))
    if u > d: continue
    if v > d: continue
    graph[u].append((v, m))
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # 우선 순위, 현재 지점
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist: continue
        for node in graph[now]:
            if dist + node[1] < distance[node[0]]:
                distance[node[0]] = dist + node[1]
                heapq.heappush(q, (dist + node[1], node[0]))

dijkstra(0)
print(distance[d])

'PS > 문제풀이' 카테고리의 다른 글

백준 1205 등수 구하기 Python  (0) 2024.01.20
백준 13549 숨바꼭질 3  (0) 2024.01.17
백준 20310 타노스 Python  (0) 2024.01.17
백준 19941 햄버거 분배 Python  (0) 2024.01.17
백준 1515 수 이어 쓰기 Python  (0) 2024.01.16