[Programmers] 합승 택시 요금

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

🤔 나의 풀이

📌 문제

- 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)

---

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

1. 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

2. 인접행렬로 나타낸 그래프로 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

---

3. 이제 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

👀플로이드 와샬 알고리즘? ← 👏🏻Click