합승 택시 요금(카카오) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

무방향 양의 가중치 그래프가 주어지고, 최소 비용을 구하는 문제이다. 따라서, 가중치 그래프의 최단 거리를 구하는 대표 알고리즘인 다익스트라, 벨만 포드, 플로이드 워셜 중 다익스트라와 플로이드 중 하나를 이용하면 된다. 그럼, 둘 중 어떤 알고리즘을 이용해야할까?

 

문제를 좀 더 분석해보면 두 사람이 [특정 노드 K]까지 합승을 한 후 K에서 A,B 노드 까지의 이동 비용을 구해야한다. 이때 각각의 [S>K], [K>A], [K>B] 로 가기 위한 여러 루트가 존재하여 각 이동에 대해 최소 거리를 구해줘야한다

---

 

또한, 전체적인 최소 비용을 구하기 위해서는 합승 노드 K를 하나씩 돌아가면서 비용을 구하고 이를 비교해줘야한다.

 

즉, [모든 노드 > 모든 노드] 로의 최단 거리가 필요하기 때문에 플로이드 워셜 알고리즘을 사용하여 모든 노드쌍에 대한 최단 거리를 구한 후, 합승 노드 K를 변경해가면서 비용을 구하고, 그 중 최솟값을 반환하면 된다.

 

 

시간 복잡도

코드 내에서 플로이드 워셜 알고리즘으로 인해 삼중 for문이 수행되기 때문에 O(n^3)의 시간이 걸리며, n의 최댓값이 200이므로 시간 내에 동작한다.

 

 

코드

INF = int(1e9)

def solution(n, s, a, b, fares):

    # 인접행렬 초기화
    adj = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
    for u, v, c in fares:
        adj[u][v] = c
        adj[v][u] = c
    for i in range(n + 1):
        adj[i][i] = 0

    # 플로이드 워셜 알고리즘 적용
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

    answer = INF
    # 모든 노드를 [합승 마지막 지점]으로 돌아가면서 설정하여 요금을 구하고, 그 중 최솟값을 찾는다.
    for k in range(1, n + 1):
        distance = adj[s][k] + adj[k][a] + adj[k][b]
        answer = min(answer, distance)

    return answer

 

 

회고

가중치 그래프가 주어졌을 때 어떤 알고리즘을 선택하여 풀지를 선정해야한다.

이전에 풀었던 문제들이 힌트를 직접적으로 던져줬었다면, 이 문제의 경우 문제를 한 층 더 깊이 분석해야 힌트가 나오는 듯한 느낌을 받았다.