내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
합승 택시 요금
ps:problems:programmers:72413
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 합승 택시 요금 ====== ===== 풀이 ===== * 합승해서 x까지 같이 간 뒤에, x에서 부터는 따로 택시를 타고 a와 b로 간다면 총 요금은 cost[s][x] + cost[x][a] + cost[x][b]. * 모든 x에 대한 cost[s][x], cost[x][a], cost[x][b]의 값을 계산해놓는다면, min_x(cost[s][x] + cost[x][a] + cost[x][b]) 는 O(n)에 계산가능 * 그냥 [[ps:APSP]] 알고리즘을 써서 cost[x][y]를 다 구해놓으면 O(n^3)으로 비효율적이지만, 통과는 된다. * 이 문제에서는 cost[...][a] = cost[a][...], 이므로 cost[a][...], cost[b][...], cost[s][...]를 각각 [[ps:단일 출발지 최단 경로#다익스트라 알고리즘]]으로 구하는 편이 좀더 효율적이다. 문제에서 E≤O(V^2)으로 주어졌으므로, 시간 복잡도를 O(ElogV)대신 O(V^2)으로 표현하는것이 더 나을듯. 실제 구현은 O(ElogV)의 구현으로 처리했다. * cost를 모두 구했으면, min을 계산하는 것은 O(n)이다. ===== 코드 ===== <dkpr py> """Solution code for "Programmers 72413. 합승 택시 요금". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/72413 - Solution link: http://www.teferi.net/ps/problems/programmers/72413 """ from teflib import tgraph def solution(n, s, a, b, fares): wgraph = [{} for _ in range(n)] for c, d, f in fares: wgraph[c - 1][d - 1] = wgraph[d - 1][c - 1] = f dists_s = tgraph.dijkstra(wgraph, s - 1) dists_a = tgraph.dijkstra(wgraph, a - 1) dists_b = tgraph.dijkstra(wgraph, b - 1) return min(dists_s[x] + dists_a[x] + dists_b[x] for x in range(n)) </dkpr> * Dependency: [[:ps:teflib:tgraph#dijkstra|teflib.tgraph.dijkstra]] {{tag>프로그래머스 ps:problems:programmers:Level_3}}
ps/problems/programmers/72413.txt
· 마지막으로 수정됨: 2024/03/14 08:35 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로