[Programmers] 합승 택시 요금

eunseo kim 👩‍💻·2021년 6월 26일

2021 KAKAO BLIND RECRUITMENT

🎁프로그래머스 도장깨기

목록 보기

4/5

🤔 나의 풀이

📌 문제

- programmers > 2021 KAKAO BLIND RECRUITMENT > 합승 택시 요금

📌 날짜

2021.06.26

📌 시도 횟수

1회 / 카카오 해설 참고 + floyd warshall 알고리즘 참고

🏆 문제 해결 방법

카카오 코딩테스트 해설을 참고했다.
Floyd Warshall 알고리즘을 이용해서 풀었다.

👊🏻 문제 해결 방법을 이해해보자.

d[i][j] = i번 지점에서 j번 지점까지 갈 때의 최저 예상 택시요금이라고 하자.

S(시작점)에서 K(A, B가 합승하는 지점의 끝)까지의 거리를 구한다.

이때 S에서 K까지의 거리는 A, B가 합승하는 거리를 의미한다.

그리고 각각의 K에 대해, K에서 A, K에서 B까지의 거리의 최소값을 구하면 된다.

이때 K는 시작점이 될 수도 있다. 즉, K = S라면 A, B가 아예 합승을 하지 않는 경우를 말한다. 아래의 입출력 예#2가 바로 S = K인 경우이다.

즉, 위의 내용을 정리하면, 문제에서 요구하는 답은 min(d[s][k] + d[k][a] + d[k][b])이다. (단, k = 1 ~ n)

👏🏻 이제 실제 코드로 구현해보자.

Floyd Warshall 알고리즘을 사용하려면 주어진 가중치 무방향 그래프를 인접행렬로 나타내야 한다.
def make_graph(n, fares):
    graph = [[0 if (i == j) else float("inf") for i in range(n)] for j in range(n)]

    for u, v, w in fares:
        graph[u - 1][v - 1] = w
        graph[v - 1][u - 1] = w

    return graph
인접행렬로 나타낸 그래프로 Floyd Warshall 알고리즘을 적용한다. Floyd Warshall 알고리즘을 적용하면, 모든 정점에서 모든 정점으로의 최단 경로를 알 수 있다.

즉, 인접행렬의 행을 i, 열을 j라고 하면 graph[i][j] = i 정점에서 j 정점까지 가는 최단 경로이다.

Floyd Warshall 알고리즘의 구현 방법은 👏🏻여기👏🏻를 참고하자.
def floyd_warshall(n, graph):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph
이제 k(합승하는 끝 정점)이 1~n일 때의 각각의 모든 경우를 검사하여, d[s][k] + d[k][a] + d[k][b]의 최소값을 구하자.
    min_fare = float("inf")
    for k in range(n):
        min_fare = min(min_fare, graph[s - 1][k] + graph[k][a - 1] + graph[k][b - 1])

✅ 최종 코드 (정확성 100 / 효율성 100)

from collections import defaultdict


def make_graph(n, fares):
    graph = [[0 if (i == j) else float("inf") for i in range(n)] for j in range(n)]

    for u, v, w in fares:
        graph[u - 1][v - 1] = w
        graph[v - 1][u - 1] = w

    return graph


def floyd_warshall(n, graph):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph


def solution(n, s, a, b, fares):
    graph = make_graph(n, fares)
    graph = floyd_warshall(n, graph)

    min_fare = float("inf")
    for k in range(n):
        min_fare = min(min_fare, graph[s - 1][k] + graph[k][a - 1] + graph[k][b - 1])
    return min_fare