합승 택시 요금 _ 카카오 코딩 테스트 (파이썬, 최단거리, 프로그래머스)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

---

풀이

import sys
input = sys.stdin.readline
INF = int(1e9)

def solution(n, s, a, b, fares):
    graph = [[INF]*(n) for _ in range(n)]
    
    for n1, n2, w in fares:
        graph[n1-1][n2-1] = w
        graph[n2-1][n1-1] = w
        
    for i in range(n):
        for j in range(n):
            if i == j:
                graph[i][j] = 0
    
    def floid(graph, n):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # k를 거쳐 가는 cost
                    cost = graph[i][k] + graph[k][j]
                    graph[i][j] = min(graph[i][j], cost)
    
        return graph
    
    def findPath(graph, n, s, a, b):
        result = graph[s-1][a-1] + graph[s-1][b-1] # 합승 안하는 경우 
        
        for k in range(n): # k 지점까지 합승 하는 경우
            shareRideCost = graph[s-1][k]
            cost = shareRideCost + graph[k][a-1] + graph[k][b-1]
            result = min(result, cost)
        
        return result
    
    graph = floid(graph, n)
    answer = findPath(graph, n, s, a, b)
    return answer

 

---

문제 접근

문제를 보자마자 !!최단거리!! 문제임을 느겼을 것이다. (node, weight 주어지고 최솟값 구하라는데 못 느꼈음 유감...) 
최단거리 유형은 6가지 정도 있고 알고리즘은 3개가 있다.

1. 다익스트라 알고리즘
- 최단거리 문제에서 가장 많이 쓰인다.
- 최단거리 알고리즘 중에서 가장 빠르다.
- 한 지점에서 다른 지점까지의 최단거리를 구할 때, 사용된다.

2. 플로이드 워셸 알고리즘
- 모든 지점에서 다른 지점들까지의 최단거리를 구할 때 사용된다.
- 다익스트라에 비해 구현이 쉽다.
- 다익스트라에 비해 시간, 공간 모두 다 불리하다.

3. 벨만 포드 알고리즘
- 세 알고리즘 중 가장 최악의 성능의 알고리즘이다.
- 음의 가중치가 있는 경우 사용된다.
- 정말 마지막의 마지막에 생각하자. 성능이 안 좋아 컴퓨터 많이 아프다.

최대한 다익스트라로 해결하려 고민해 보았으나 
"합승" 이란 조건 때문에 다익스트라보다는 플로이드 워셸 알고리즘이 적절하다고 판단했다.

1. "합승"을 k 까지 한다. => 이때 cost 계산
2. k에서 각자 도착지점 까지 간다. => 이때 cost A, cost B를 계산한다.
3. cost + costA + costB 합이 가장 작은 값이 answer

즉, 모든 지점에서 다른 모든 지점의 최단 거리가 필요했다.