[프로그래머스] 합승 택시 요금 / Python

문제주소 :programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

---

<문제 설명>

[문제]

지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.
만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

[제한사항]

• 지점갯수 n은 3 이상 200 이하인 자연수입니다.
• 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
  • 즉, 출발지점, A의 도착지점, B의 도착지점은 서로 겹치지 않습니다.
• fares는 2차원 정수 배열입니다.
• fares 배열의 크기는 2 이상 n x (n-1) / 2 이하입니다.
  • 예를들어, n = 6이라면 fares 배열의 크기는 2 이상 15 이하입니다. (6 x 5 / 2 = 15)
  • fares 배열의 각 행은 [c, d, f] 형태입니다.
  • c지점과 d지점 사이의 예상 택시요금이 f원이라는 뜻입니다.
  • 지점 c, d는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
  • 요금 f는 1 이상 100,000 이하인 자연수입니다.
  • fares 배열에 두 지점 간 예상 택시요금은 1개만 주어집니다. 즉, [c, d, f]가 있다면 [d, c, f]는 주어지지 않습니다.
• 출발지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.

---

[입출력 예]

n                        s                      a                        b                      fares                  result

6	4	6	2	[[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]]	82
7	3	4	1	[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]]	14
6	4	5	6	[[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4,8], [4,3,9]]	18

입출력 예에 대한 설명

---

입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2

• 합승을 하지 않고, B는 3→2→1, A는 3→6→4 경로로 각자 택시를 타고 가는 것이 최저 예상 택시요금입니다.
• 따라서 최저 예상 택시요금은 (3 + 6) + (1 + 4) = 14원 입니다.

입출력 예 #3

• A와 B가 4→6 구간을 합승하고 B가 6번 지점에서 내린 후, A가6→5` 구간을 혼자 타고 가는 것이 최저 예상 택시요금입니다.
• 따라서 최저 예상 택시요금은 7 + 11 = 18원 입니다.

 

<풀이법>

▒ 한줄 개념: 플로이드 알고리즘 ▒ 

플로이드 (플로이드-와샬)알고리즘 또는 다익스트라 알고리즘으로 풀 수 있는 문제입니다.

플로이드 알고리즘으로 풀 경우 n^3의 시간 복잡도가 소요되며, 다익스트라 알고리즘으로 풀 경우 n^2의 시간 복잡도가 소요됩니다.

플로이드 알고리즘은 시간 복잡도가 큰 만큼 N이 많을 경우 사용할 수 없지만, 이 문제에서는 N이 최대 200이므로 플로이드 알고리즘의 사용이 가능했습니다.

 

따라서 더 구현이 간단한 플로이드 알고리즘을 사용해 풀었고, 풀이방식은 다음과 같습니다.

• 초기화
  • n*n의 matrix를 만들고, math.inf를 통해 초기화
  • fares 배열의 값들을 matrix내 해당 위치에 삽입
• 각 점사이의 최소 비용 계산
  • 플로이드 알고리즘을 사용하여 모든 점 사이의 최소 비용을 계산
• min_cost 계산
  • matrix[s][a] + matrix[s][b] 로 초기화 : 일단은 a,b 모두 따로 가는 비용으로 시작
  • 반복문을 통해 matrix[s][path] + matrix[path][a] + matrix[path][b] 와 비교 : 경유지(path)를 거쳐 가는 경우의 비용 체크

 

+++ 정확성 10, 효율성 3,16,17,18,25,26 실패 +++

이 문제에서 주의할 점은 inf의 값을 정해주는 것입니다. 비용 f는 최대 100,000씩, 최대 200개의 N이 있으므로 min_cost의 최댓값은 매우 커질 수 있습니다.(20,000,000?)  따라서 내부 모듈의 inf 값을 통해 확실한 값으로 matrix를 초기화해주는 것이 좋습니다.

 

<코드(Python)>

import math

def solution(n, s, a, b, fares):
    s, a, b = s - 1, a - 1, b - 1
    inf = math.inf   # 무한대값으로 초기화
    matrix = [[inf for i in range(n)] for j in range(n)]
    
    for f in fares:  # fares 배열 값 삽입
        matrix[f[0] - 1][f[1] - 1] = f[2]
        matrix[f[1] - 1][f[0] - 1] = f[2]

    for path in range(n):  # 플로이드 알고리즘
        for head in range(n):
            for tail in range(n):
                if head == tail:
                    matrix[head][tail] = 0 
                elif matrix[head][tail] > matrix[head][path] + matrix[path][tail]:
                    matrix[head][tail] = matrix[head][path] + matrix[path][tail]

	# 최소값 계산
    min_cost = matrix[s][a] + matrix[s][b]   # 직접 가는 비용으로 초기화
    for path in range(n):
        if min_cost > matrix[s][path] + matrix[path][a] + matrix[path][b]:
            min_cost = matrix[s][path] + matrix[path][a] + matrix[path][b]

    return min_cost

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest