[Programmers] 합승 택시 요금 (파이썬, Python)

https://pixabay.com/ko/photos/꽃-식물-선셋-노란-꽃-6339436/

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

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

이 문제는 프로그래머스의  2021 KAKAO BLIND RECRUITMENT 문제집에 속해 있는 문제입니다.

 

문제에서는 출발지(S)와 각각의 목적지(A와 B)가 주어지고, 출발지에서 두 목적지를 방문하기까지의 최소 비용(=최단 거리)을 구하는 것이 문제의 목표입니다.

 

해당 문제는 그래프의 최단 거리 문제로 이용할 수 있는 알고리즘은 다익스트라 알고리즘과 플로이드 와샬 알고리즘이 있습니다.

 

저는 플로이드 와샬 풀이 법을 선택했고, 그래프 최단 거리 문제와 알고리즘이 익숙하지 않아서 따로 공부를 한 후 문제에 도전했습니다.

 

플로이드 와샬 알고리즘 공부하고 연습이 필요하신 분은 아래의 문제를 먼저 푸는 것도 좋을 거 같습니다😊

https://www.acmicpc.net/problem/11404

 

접근 방식

1. 플로이드 와샬 알고리즘을 이용해서 모든 정점에서 모든 정점으로의 최단 거리를 계산

2. 초기 answer에 각각의 목적지로 합승하지 않고 따로 갈 때의 비용을 저장

3. 1 ~ n의 지점 각각을 한 번씩 경우지로 지정하고 출발 지점(S)에서 경유지를 들려 각각의 목적지로 가는 비용과 현재의 answer값과 비교 후 최솟값을 answer에 저장

3번 단계에서 사용된 비교식
answer = min(answer, 비용[S -> (경유지)] + 비용[(경유지) -> A] + 비용[(경유지) -> B])

전체 코드

def calculate(n, dist):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    
def solution(n, s, a, b, fares):
    answer = 0
    
    dist = [ [ float('inf') ] * n for _ in range(n) ]
    
    for i in range(n):
        dist[i][i] = 0
        
    for fare in fares:
        c, d, f = fare
        
        dist[c-1][d-1] = f
        dist[d-1][c-1] = f
    
    
    calculate(n, dist)
    
    answer = dist[s-1][a-1] + dist[s-1][b-1]
    
    for i in range(n):
        answer = min(answer, dist[s-1][i-1]+dist[i-1][a-1]+dist[i-1][b-1])
    
        
    return answer

---

읽어 주셔서 감사합니다 :)

잘못된 부분이 있다면 댓글로 편히 알려주세요😊