[프로그래머스] 합승택시요금 .py

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

 

 

 

1. 모든 간선들에 대한 최단거리 테이블을 갱신

2. 출발지점 s 에서 공통경로 i + 공통경로 i 에서 a + 공통경로  i 에서 b 최단거리 갱신

 

 

 

 

최단경로 알고리즘은 '다익스트라'와 '플로이드 워셜' 2가지가 있다.

 

다익스트라 (우선순위 큐)

단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택한 뒤에, 그 노드를 거쳐 가는 경우를 구하여 최단거리 갱신

시간복잡도 - O(V^2), O(ElogV) # 선형탐색 시, heap 사용시

 

플로이드 워셜 (3중 for문)

거쳐 가는 노드를 기준으로 최단거리 테이블을 갱신 

시간복잡도 - O(V^3)

 

n의 크기가 300 이하이기도 하고 다익스트라보다는 플로이드워셜이 더 쉬우니 플로이드 워셜로 풀어보도록 하겠다.

def solution(n, s, a, b, fares):
    INF = 1e9
    adj = [[INF for _ in range(n + 1)] for _ in range(n + 1)]

    for v1, v2, cost in fares:
        adj[v1][v2] = cost
        adj[v2][v1] = cost

    for k in range(1, n + 1):
        for v1 in range(1, n + 1):
            for v2 in range(1, n + 1):
                if v1 == v2:
                    adj[v1][v2] = 0
                    continue
                
                # 주의
                if adj[v1][v2] > adj[v1][k] + adj[k][v2]:
                    adj[v1][v2] = adj[v1][k] + adj[k][v2]
                
                
    answer = adj[s][a] + adj[s][b]
    for i in range(1, n + 1):
        answer = min(answer, adj[s][i] + adj[i][a] + adj[i][b])
        
    return answer

 

여기서 주의해주어야 할 점은, # 주의 부분을 adj[v1][v2] = min(adj[v1][v2], adj[v1][k] + adj[k][v2])로 써주자, 효율성에서 하나가 통가되지 못하였다. 정말 시험이었다면 이거 하나로 고치지 힘들었을텐데, 만약 다음번에 min을 써서 시간초과가 났다면 # 주의 부분과 같이 고쳐보도록 해야겠다.