[Swift - 프로그래머스] 합승 택시 요금

🕵🏻  문제 해석 

---

무지와 어피치는 최근 잦아진 야근 때문에 택시를 타고 귀가하는 일이 늘어났습니다. 그래서 택시를 같이 타고 귀가하여 요금을 최대한 줄여보려고 합니다. 함께 출발하는 지점 s, 그리고 각자의 집이 위치하는 a, b 지점과 지점과 지점 사이의 예상요금이 fare 배열로 주어질 때 최소요금을 계산해봅시다.

[제한사항]

• 지점갯수 n은 3 이상 200 이하인 자연수입니다.
• 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
• 출발지점, A의 도착지점, B의 도착지점은 서로 겹치지 않습니다.
• 요금 f는 1 이상 100,000 이하인 자연수입니다.
• 출발지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.

 

🤔 풀이 과정

---

먼저 문제를 읽고 그래프 문제라는 것을 쉽게 알 수 있었습니다. 출발지는 s 하나로 단일 출발지의 최단 경로를 구하는 문제라고 볼 수 있습니다. 그리고 간선인 도로가 양방향이라고 하는군요. 다익스트라 알고리즘과 플로이드 와샬 알고리즘으로 최단 경로를 구해 볼 수 있는데, 해당 문제에서는 지점의 최대 개수가 200 이므로 시간 복잡도가 O(V3)인 플로이드 와샬로 접근해보았습니다. 

그럼 간선의 최댓값을 구해주어 인접 매트릭스를 초기화해주어야 하는데, 저 같은 경우는 모든 지점과 간선이 일직선상에 위치할 때, 첫 번째 지점과 끝 지점 사이의 거리가 최대가 된다고 생각했습니다. 따라서 지점의 최대 개수가 200이고 간선의 최대 길이가 10만이므로 최대 길이(최대 요금)는 2천만 미만(200 * 100000)이겠죠? 

(N + 1) X (N + 1) 크기의 2차원 행렬을 최댓값으로 초기화시켜주고 fare배열을 탐색하며 경로마다 그 값을 갱신해주었습니다. 그 후 플로이드 와샬 알고리즘으로 각 지점 간 최소 길이(요금)를 구해주고 1부터 n 지점 사이를 중간 지점으로 지정한 후 하나하나씩 값을 비교하여 최소 요금을 구해보았습니다.

 

📦  문제 풀이 & 코드

---

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    // 최대 요금, 최대요금으로 인접 매트릭스 초기화
    let maxFare = 200 * 100000
    var graph = [[Int]](repeating: [Int](repeating: maxFare, count: n + 1), count: n + 1)
    var answer = Int.max

    for fare in fares {
        let from = fare[0]
        let to = fare[1]
        let cost = fare[2]
        
        // 양방향 그래프
        graph[from][to] = cost
        graph[to][from] = cost
    }
    // 자기 자신까지의 요금는 0
    for node in 1...n {
        graph[node][node] = 0
    }

    // 플로이드 와샬: k 지점을 거쳐가는 경우가 요금이 싸다면, 갱신
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            }
        }
    }
    // 중간지점을 하나씩 설정하여 최솟값을 구함. 출발지에서 각자 출발하는 경우도 포함 (mid == s)
    for mid in 1...n {
        answer = min(answer, graph[s][mid] + graph[mid][a] + graph[mid][b])
    }

    return answer
}

https://programmers.co.kr/learn/courses/30/lessons/72413

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