programmers.co.kr/learn/courses/30/lessons/72413
- 각 지점은 1 ~ n으로 표시
- s에서 출발해서 도착지는 각각 a와 b
- 지점 사이의 예상 택시 요금을 나타내는 fares
- 만약 합승하지 않고 각자 이동하는 경우가 더 저렴하면 합승하지 않아도 된다
- 양방향
- 3 <= n <= 200 인 자연수
- 1 <= s, a, b <= n 인 자연수이고 모두 다른 값이다
from heapq import heappush, heappop
def solution(n, s, a, b, fares):
INF = 0
adj = [[] for _ in range(n+1)]
for c, d, f in fares:
adj[c].append([d, f])
adj[d].append([c, f])
INF += f
def fee(i, j): # i에서 j로 가는 최소 요금 계산
Q = []
visited = [INF] * (n+1)
heappush(Q, [0, i])
visited[i] = 0
while Q:
p, v = heappop(Q)
if p > INF: continue
if visited[v] < p: continue
for w, wp in adj[v]:
np = p + wp
if visited[w] > np:
visited[w] = np
heappush(Q, [np, w])
return visited[j]
sa = fee(s, a)
sb = fee(s, b)
ab = fee(a, b)
ba = fee(b, a)
answer = min(sa+sb, sa+ab, sb+ba)
INF = answer
for i in range(n+1): # s->i + i->a + i->b
if i in [s, a, b]: continue
tmp = fee(s, i)
if tmp >= answer: continue
tmp += fee(i, a)
if tmp >= answer: continue
tmp += fee(i, b)
if tmp < answer:
answer = tmp
INF = answer
return answer
이 문제는 정확성과 효율성을 모두 살피는 문제였다
처음 문제를 읽고 플로이드-와샬
문제라고 생각했지만 아직 해당 알고리즘을 공부하지 못했기 때문에 heapq를 이용하여 문제를 해결하고자 했다
오랜만에 heapq를 활용한 문제를 풀어서 코드가 덕지덕지인 느낌이다 그래서 효율적이지 못한 느낌.
다음에 조금 더 효율적인 방법이 없는지 알아봐야겠다
정확성 테스트
테스트 1 〉 통과 (0.06ms, 10.2MB) 테스트 2 〉 통과 (0.07ms, 10.5MB) 테스트 3 〉 통과 (0.04ms, 10.3MB) 테스트 4 〉 통과 (0.31ms, 10.4MB) 테스트 5 〉 통과 (0.24ms, 10.3MB) 테스트 6 〉 통과 (0.42ms, 10.3MB) 테스트 7 〉 통과 (0.43ms, 10.1MB) 테스트 8 〉 통과 (0.49ms, 10.2MB) 테스트 9 〉 통과 (0.65ms, 10.3MB) 테스트 10 〉 통과 (0.79ms, 10.4MB)
효율성 테스트
테스트 1 〉 통과 (28.83ms, 10.3MB) 테스트 2 〉 통과 (212.08ms, 10.7MB) 테스트 3 〉 통과 (71.25ms, 10.4MB) 테스트 4 〉 통과 (55.51ms, 10.3MB) 테스트 5 〉 통과 (82.95ms, 10.4MB) 테스트 6 〉 통과 (80.05ms, 10.3MB) 테스트 7 〉 통과 (2399.91ms, 16MB) 테스트 8 〉 통과 (2331.34ms, 16.1MB) 테스트 9 〉 통과 (1966.60ms, 16.1MB) 테스트 10 〉 통과 (1898.15ms, 16MB) 테스트 11 〉 통과 (1824.10ms, 16.1MB) 테스트 12 〉 통과 (1207.62ms, 13.1MB) 테스트 13 〉 통과 (1043.78ms, 13.2MB) 테스트 14 〉 통과 (998.45ms, 13.2MB) 테스트 15 〉 통과 (1078.97ms, 13.2MB) 테스트 16 〉 통과 (80.20ms, 10.2MB) 테스트 17 〉 통과 (78.03ms, 10.2MB) 테스트 18 〉 통과 (89.42ms, 10.3MB) 테스트 19 〉 통과 (163.27ms, 10.5MB) 테스트 20 〉 통과 (231.44ms, 10.7MB) 테스트 21 〉 통과 (219.54ms, 10.6MB) 테스트 22 〉 통과 (1333.76ms, 13.2MB) 테스트 23 〉 통과 (1176.34ms, 13.2MB) 테스트 24 〉 통과 (1064.85ms, 13.1MB) 테스트 25 〉 통과 (45.62ms, 10.2MB) 테스트 26 〉 통과 (52.09ms, 10.2MB) 테스트 27 〉 통과 (243.19ms, 10.7MB) 테스트 28 〉 통과 (250.71ms, 10.5MB) 테스트 29 〉 통과 (25.48ms, 10.3MB) 테스트 30 〉 통과 (26.85ms, 10.2MB)