[Python] 프로그래머스 - 합승 택시 요금
https://programmers.co.kr/learn/courses/30/lessons/72413
# 2021 카카오 블라인드 코딩테스트 문제이다.
# 그냥 문제를 보면 '그래프' 문제인 것을 알 수 있다.
# N이 200이하이므로 O(N^3)인 플로이드-와샬 알고리즘이랑 O(E logV)인 다익스트라를 생각해볼 수 있다.
1. 플로이드-와샬
* 그래프탐색의 완전탐색이라고 할 수 있는 플로이드-와샬이다.
1-1. fares에 있는 지점들 사이의 택시요금 cost를 갱신해주고 floyd_warshall함수를 실행한다.
1-2. floyd_warshall함수: k를 1부터 n번 지점까지 돌면서 i에서 k를 거쳐 j까지 가는 cost를 갱신해준다.
1-3. i를 A와 B가 같이가는 지점이라고 가정하고, 1부터 n까지 반복문을 돌며
s에서 i까지의 비용 + i에서 a까지의 비용 + i에서 b까지의 비용을 구해 ans와 비교해 작은 값을
ans에 넣어준다. 모든 지점을 다 확인한 뒤 ans를 return해준다.
def solution(n, s, a, b, fares):
ans = 200000001
cost = [[20000001] * (n+1) for _ in range(n+1)]
def floyd_warshall():
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if i == j:
cost[i][j] = 0
else:
cost[i][j] = min(cost[i][k] + cost[k][j], cost[i][j])
for i, j, c in fares:
cost[i][j] = c
cost[j][i] = c
floyd_warshall()
for i in range(1, n+1):
ans = min(cost[s][i] + cost[i][a] + cost[i][b], ans)
return ans
========================================================================
2. 다익스트라
# 대부분의 케이스에서 플로이드-와샬보다 빠른속도를 보여주었지만
케이스 하나에서 3700ms가 나왔다. 간선의 개수가 많아지면 더 느려지는 것 같다.
# 플로이드와샬 (270ms ~ 2300ms), 다익스트라 (15ms ~ 1600ms, 3700ms)
import heapq
def solution(n, s, a, b, fares):
def dijkstra(start):
res = [float('INF') for _ in range(n+1)]
res[start] = 0
q = []
heapq.heappush(q, (res[start], start))
while q:
result_x, x = heapq.heappop(q)
for fu, fw in graph[x]:
if res[fu] > result_x + fw:
res[fu] = result_x + fw
heapq.heappush(q, ([res[fu], fu]))
return res
ans = 200000001
graph = [[] for _ in range(n+1)]
for i, j, c in fares:
graph[i].append((j, c))
graph[j].append((i, c))
dist = [[]]
for i in range(1, n+1):
dist.append(dijkstra(i))
for i in range(1, n+1):
ans = min(ans, dist[s][i] + dist[i][a] + dist[i][b])
return ans
(프로그래머스 level: 3)
'문제풀이 > Programmers' 카테고리의 다른 글
[Python] 프로그래머스 - 메뉴 리뉴얼 (0) | 2021.09.03 |
---|---|
[Python] 프로그래머스 - Weekly Challenge 5주차 (0) | 2021.08.31 |
[Python] 프로그래머스 - Weekly Challenge 4주차 (0) | 2021.08.28 |
[Python] 프로그래머스 - 괄호 변환 (1) | 2021.08.27 |
[Python] 프로그래머스 - 문자열 압축 (0) | 2021.08.26 |