백준 1916 - 최소비용 구하기 (Python)

BOJ PS/Python 2022. 12. 8. 16:54

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

가중치가 양수일 때 사용할 수 있는 다익스트라 알고리즘을 공부했다.

개념이 어려웠다기보단 적용이 조금 헷갈리는 부분이 많았다.

이 방법의 핵심은, heap 안에 현재 가중치와 현재 지점을 넣으며 최소 비용을 업데이트하는 것이다.

s[cur_d] 안에는 cur_d에서 출발하여 도착할 수 있는 지점들이 있다.

따라서 cur_d에서 갈 수 있는 지점들을 체크해주며 그 지점까지의 최소 비용을 구해준다.

이 과정에서 만약 애초에 cur_w, 즉 현재 가중치가 그 지점의 가중치보다 크다면 이야기가 달라진다.

그 지점을 출발점으로 하여 업데이트해줄 이유도 없다.

왜냐하면 현재 우리는 heap을 이용하여 애초에 값을 뽑을 때 가중치가 낮은 순으로 뽑고 있기 때문이다.

여러모로 특이한 개념들이 섞여 있어 계속 다시 공부해주어야 할 것 같다.

생각 생각