[프로그래머스] 합승 택시 요금, Python3

문제는 여기!

 

안녕하세요! 이번 포스팅에서는 2021 카카오 블라인드 채용 문제인 "합승 택시 요금" 문제를 풀어보겠습니다. 2021년도 Level3 문제들 중에서 체감 상 가장 난이도가 낮은 것 같았습니다.

형냐들 나만그래?

최단 거리 문제를 살짝 응용하면 쉽게 풀 수 있는 문제라서 바로 풀이로 넘어가 보도록 하겠습니다.

제한사항 및 주의사항

지점 간 택시가 이동할 수 있는 경로를 간선이라고 하며, 간선에 표시된 숫자는 두 지점 사이의 예상 택시요금을 나타냅니다. 또한 이동방향에 따라 금액이 달라지지 않습니다.

지점의 갯수 n은 3이상 200 이하입니다.

s, a, b는 1 ~ n까지의 범위이며, 서로 겹치지 않습니다.

fares의 크기는 2 이상 n * (n - 1) / 2 이하입니다.

fares의 각 행은 [c, d, f]이며, c지점과 d지점 사이의 예상 택시요금이 f원 이라는 뜻입니다.

요금 f는 1 ~ 100,000 이하인 자연수 입니다.

풀이전략

최단거리 문제로써, 플로이드 와샬 혹은 다익스트라로 풀이할 수 있는 문제입니다. 저는 다익스트라 알고리즘을 이용해 풀이했습니다.

주어진 fares 배열을 양방향 인접 리스트로 표현합니다. 예를 들어, 1 지점에서 2 지점까지 10의 택시요금이 든다면

graph[1].append([10, 2])

graph[2].append([10, 1])

이런 식으로 표현합니다.

왜 [요금, 도착지점] 의 형태로 append 했나요?

다익스트라 알고리즘으로 최단 거리를 구할 때, heapq(우선순위 큐) 를 이용해서 갈 수 있는 지점들 중, 요금이 가장 저렴한 지점부터 탐색하기 위해서 입니다.

우리는 우선 두 경우를 각각 구해서 최솟값을 반환해야 합니다.

1. 무지, 어피치 즈그들 각자 갈 경우
2. 무지, 어피치가 같이 합승해서 가는 경우

1번의 경우는 dijkstra(우리가 만든 인접 리스트, 시작지점, a의 도착지점) = a가 도착 지점까지 갈 수 있는 최단 거리 반환과 dijkstra(우리가 만든 인접 리스트, 시작지점, b의 도착지점) = b가 도착 지점까지 갈 수 있는 최단 거리 반환을 더해주면 됩니다.

2번의 경우는 1부터 n까지 반복문(i)을 통해 dijkstra(우리가 만든 인접 리스트, 시작지점, i) = 시작 지점부터 i번째 지점까지 a와 b가 함께 가는 경우 + dijkstra(우리가 만든 인접 리스트, i, a) = i번째 지점부터 a가 목적지 까지 가는 경우 + dijkstra(우리가 만든 인접 리스트, i, b) = i번째 지점부터 b가 목적지 까지 가는 경우를 하나씩 최솟값을 구해줍니다. 이때 i가 s와 같은경우는 제외해주는 센스는 잊지 말긔!

다익스트라 알고리즘에 대한 설명은 저보다 다른 블로그들에서 설명이 너무 잘되어있기 때문에 코드로 대체합니다. 피드백은 언제나 환영해요!

from heapq import heappush, heappop


def dijkstra(graph, start, destination):
    INF = int(1e9)
    distance = [INF for _ in range(len(graph))]
    distance[start] = 0
    heap = [[0, start]]
    while heap:
        dist, now = heappop(heap)
        if distance[now] < dist:
            continue

        for cost, next_point in graph[now]:
            next_dist = cost + dist
            if distance[next_point] > next_dist:
                distance[next_point] = next_dist
                heappush(heap, [next_dist, next_point])

    return distance[destination]


def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n + 1)]
    for p1, p2, fare in fares:
        graph[p1].append([fare, p2])
        graph[p2].append([fare, p1])

    # 우선 각자 갈 경우
    answer = dijkstra(graph, s, a) + dijkstra(graph, s, b)

    # start를 제외하고 한 point까지 무지와 어피치가 같이가는 경우
    for i in range(1, n + 1):
        if i != s:
            answer = min(answer, dijkstra(graph, s, i) + dijkstra(graph, i, a) + dijkstra(graph, i, b))

    return answer