반응형
https://www.acmicpc.net/problem/16681
16681번: 등산
첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤
www.acmicpc.net
소스코드
풀이
★ 집에서 목표지점으로 갈 때와 목표지점에서 고려대학교로 갈 때의 조건이 달라서 처음엔 함수를 2개 만들어야하나 싶었습니다. 근데 조건을 보면 집과 고려대학교의 높이가 모두 1이기 때문에 역으로 생각해보면, 각각의 지점에서부터 목표까지 가는 방향의 높이는 모두 증가하기에 집 -> 목표 조건 성립, 목표 -> 고려대학교 조건이 성립합니다.
★ 그렇기에 다익스트라를 구현하면서 해당 정점의 높이가 그 다음 정점의 높이보다 작은 경우에만 힙에 푸쉬를 하는 방식으로 구현하였습니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 12834번: 주간 미팅 (Python) (1) | 2023.11.27 |
|---|---|
| [백준 알고리즘] 5719번: 거의 최단 경로 (Python) (2) | 2023.11.27 |
| [백준 알고리즘] 1753번: 최단경로 (Python) (1) | 2023.11.21 |
| [백준 알고리즘] 1652번: 누울 자리를 찾아라 (Python) (0) | 2023.11.20 |
| [백준 알고리즘] 14938번: 서강그라운드 (Python) (1) | 2023.11.20 |