다익스트라
-
[프로그래머스] 합승 택시 요금 / KAKAO BLIND RECRUITMENT / 파이썬알고리즘/프로그래머스 2021. 2. 22. 12:57
문제 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 1. 택시가 이동할 수 있는 경로 마다 예상 택시 요금이 있는데 a와 b가 s에서 출발하여 가장 적은 요금으로 둘 다 귀가를 하는 것이 목적입니다. 2. 지점 별로 최소 예상..
-
[백준] 1162 도로포장 파이썬알고리즘/백준 2021. 2. 19. 18:41
문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 풀이 1. 서울에서 시작하여 포천까지 최소 시간이 걸리도록 해야합니다. 2. 도시별로 최소 시간을 구하기 위해서 다익스트라 알고리즘을 구현합니다. 3. 주의할 점은 K개를 사용해서 거리를 포장하면 시간이 0이 되기 때문에 이 부분을 구현해야 합니다. 4. 구현하는 방법은 도시별의 최소 시간과 도시별 방문 유무 리스트를 2차원(N * K)으로 늘려주면 됩니다. 포천에서 1 ~ K번 포장했을 때의 최단시간을 구해주고 그중 최..