programmers.co.kr/learn/courses/30/lessons/72413
경로의 최소비용 찾기 문제
다익스트라 알고리즘이나 플로이드 와샬 알고리즘을 사용해서 풀 수 있다.
코드는 모든 경로의 최소비용을 구하는 플로이드 와샬이 더 깔끔하지만 속도는 다익스트라가 훨씬 빠르다.
<Dijkstra>
3*O(n^2)
import copy
def solution(n, s, a, b, fares):
MAX = 100001*200
nodes = [[MAX for _ in range(n+1)] for __ in range(n+1)]
for c,d,f in fares: nodes[c][d] = nodes[d][c] = f
costs = copy.deepcopy(nodes)
for _s in [s,a,b]:
toVisit = set({i+1 for i in range(n)})
toVisit.remove(_s)
costs[_s][_s] = 0
while toVisit:
_min, minidx = MAX, 0
for i in toVisit:
if costs[_s][i]<_min:
_min, minidx = costs[_s][i], i
if minidx == 0: break
toVisit.remove(minidx)
for i in toVisit:
costs[_s][i] = min(costs[_s][i], costs[_s][minidx] + nodes[minidx][i])
answer = costs[s][a]+costs[s][b]
for i in range(1,n+1):
answer = min(answer,costs[s][i]+costs[a][i]+costs[b][i])
return answer
<Floyd-Warshall>
O(n^3)
def solution(n, s, a, b, fares):
MAX = 100001*200
nodes = [[MAX for _ in range(n+1)] for __ in range(n+1)]
for c,d,f in fares: nodes[c][d] = nodes[d][c] = f
for i in range(n): nodes[i+1][i+1] = 0
for i in range(1,n+1):
for j in range(1,n+1):
for k in range(1,n+1):
if nodes[j][k] > nodes[j][i] + nodes[i][k]:
nodes[j][k] = nodes[j][i]+nodes[i][k]
answer = nodes[s][a]+nodes[s][b]
for i in range(1,n+1):
if answer > nodes[s][i]+nodes[a][i]+nodes[b][i]:
answer = nodes[s][i]+nodes[a][i]+nodes[b][i]
return answer
'PROGRAMMERS' 카테고리의 다른 글
[프로그래머스] - 매출 하락 최소화 (LEVEL 4) (0) | 2021.03.16 |
---|---|
[프로그래머스] - 지형 이동 (LEVEL4) (0) | 2021.03.11 |
[프로그래머스] - 외벽 점검 (LEVEL 3) (0) | 2021.03.11 |
[프로그래머스] - 매칭 점수 (LEVEL 3) (0) | 2021.03.10 |
[프로그래머스] - 징검다리 건너기 (LEVEL3) (0) | 2021.02.15 |
댓글