[ 프로그래머스 / LV3 / 파이썬 Python ] 합승 택시 요금

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

프로그래머스

 

코드

---

def solution(n, s, a, b, fares):
    
    MAX = float("inf")
    dp = [[MAX] * (n+1) for _ in range(n+1)]
    for A,B,w in fares:
        dp[A][B] = w
        dp[B][A] = w    
    
    for i in range(1,n+1):
        dp[i][i] = 0 
    
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])

    answer = 1e9      
    for x in range(1,n+1):
        if (res:=dp[x][a]+dp[x][b]+dp[s][x]) < answer:
            answer = res
    
    return answer

 

풀이

---

'''
플로이드 워샬로 모든 점에서 모든 지점으로 향하는 최단거리를 구한다.
(출발점 -> 특정지점) + (특정지점 -> A도착점) + (특정지점 -> B도착점)의 최소값을 구한다.
생각해볼 수 있는 경우는 다음과 같다.
1. A나 B가 가는 길에 B나 A가 중간에 내리는 경우 -> 탐색하다가 A나 B의 도착점이 있는지 확인
2. A와 B가 처음부터 다른 방향으로 가야하는 경우
3. A와 B가 함께 가다가 중간에 흩어지는 경우
그렇다면 어떤 점에서 다른 점으로 향하는 최단거리들을 구해 그 합이 최소인 것을 찾는다.
'''

위의 내용은 내가 문제를 보고 풀이에 앞서 생각한 내용들을 정리한 것이다.

 

A와 B가 특정 지점 x까지 합승하게 된다면 x에서 A, x에서 B 모두 최단거리여야 한다고 생각했다. 또한 s에서 x까지도 최단거리여야 한다.

플로이드 워샬로 모든 지점에서 모든 지점으로 향하는 최단거리를 구해낸다면 합승이 끝나는 지점 x 만 찾아내면 된다고 생각했다.

 

따라서 모든 점 x를 탐색하며 s->x, x->a, x->b의 합이 최소인 경우를 찾아냈다.