[2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금

문제 설명

프로그래머스

---

풀이 방법

• 접근 방식

    ◦  그래프 최단거리로 접근하는 문제이다.

    ◦  먼저 그래프상의 노드간의 최단거리를 계산해 문제를 간단하게 구조화 한 다음 필요한 처리를 추가해주자.

 

• 핵심 아이디어

    ◦  무지와 어피치가 헤어지는 지점을 어디로 했을 때 택시요금이 최저가 되는지를 찾으면 된다.

    ◦  즉 (시작점 ~ 헤어지는 지점) + (헤어진 지점 ~ 무지의 집) + (헤어진 지점 ~ 어피치의 집) 이 최저가 되는 헤어지는 지점을 찾는 문제

 

• 알고리즘

    ◦  floyd warshall 알고리즘을 사용해 먼저 노드간의 최단거리 연산을 해주었다.

    ◦  그 다음 모든 노드에 대해 해당 노드가 헤어지는 지점일 때의 택시 요금을 비교하여 최저가 되는 상황의 요금을 구했다.

---

파이썬 코드

def solution(n, s, a, b, fares):
    # set variables
    INF = int(1e9)
    graph = [[INF] * (n) for i in range(n)]
    
    # initialize
    for i in range(0,n):
        graph[i][i] = 0
    
    # 간선 정보 입력
    for i in fares:
        graph[i[0]-1][i[1]-1] = i[2]
        graph[i[1]-1][i[0]-1] = i[2]
    
    # floyd warshall 알고리즘
    for i in range(n):
        for j in range(n):
            for k in range(n):
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
    
    # 최단거리 탐색
    minPath = INF
    for i in range(n):
        minPath = min(minPath, graph[s-1][i] + graph[i][a-1] + graph[i][b-1])
    return minPath