반응형
최소 비용 경로
-
프로그래머스 Lv.3) 배달알고리즘/프로그래머스 2020. 5. 31. 23:03
배달 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 풀이 문제를 보고 많은 생각이 스쳐 지나갔다. MST가 먼저 떠올랐는데, 모든 경로를 잇는 것이 중요한 문제가 아니기 때문에 아니라고 생각했다. 다음은, 최단 거리 알고리즘이었다. 다익스트라(dijkstra) 이름이 기억나지 않았지만, 이 로직이 떠올랐다. 하지만, 처음에 풀었을 때는 edge를 따로 저장하지 않고, 주어진 road만 돌면서 우선순위 큐에 저장하고 최소 비용으로 잘 잇는다면 가능하지 않을까 싶었다. 결과는 40점, ..