[프로그래머스] - 합승 택시 요금 (LEVEL3)

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