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

문제

프로그래머스

입력

n:Int = 지점 개수  1<= n <= 200
s:Int = 출발 지점
a:Int = a 도착지점 
b:Int = b 독착지점
fares:[[Int]] = [[c,d,f]] 구조, c지점 <-> d지점 편도 택시 비용

 

결과

ans = a와 b가 s에서 출발해서 각자 도착지점까지 갔을 때 최소 택시 비용

해석

지점이 많지않고 몇개의 지점을 거치더라도 최소 비용으로 가기만하면 되기때문에

플로이드 와샬 알고리즘으로 접근해보자.

 

플로이드 와샬의 단계는 다음과 같다.

 

1. adj 인접배열 초기화

• 자기 자신에게는 항상 최소이므로 0
• 나머지는 INF로 초기화한다.

2. 모든 지점간 최소비용으로 adj 배열을 갱신한다. 이 때 dp를 이용하며 점화식은 다음과 같다.

adj[i][j] =  i에서 j까지 가는데 최소비용
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]) 현재 최소비용과  i->k , k->j를 거쳐갔을 때 비용 중 최소비용을 선택한다.

 

이후 모든 지점에 대해 최소비용을 계산하게 되면 이제 택시비용을 구할 수 있는 준비가 갖쳐졌다.

 

여기서 나는 a와 b가 어디서 해어져야 가장 싼 택시비용인지로 시점을 바꾸면 답이 바로 나왔다.

 

즉 헤어지는 지점을 찾아야햔다. 그러면 지점은 1~n개 이므로 그냥 돌아서 ((O(n)))이면 충분할 것 같다.

 

그러면 그 지점을 찾는 점화식은 다음과 같다.

 

ans = min(ans, adj[s][i] + adj[i][a] + adj[i][b])

adj[s][i] = 헤어지는 지점까지 같이 타고간 비용
adj[i][a] = 헤어진 지점부터 도착지점 a까지 따로 타고간 비용
adj[i][b] = 헤어진 지점부터 도착지점 b까지 따로 타고간 비용

코드

import Foundation

let MAX = 1000000

var adj: [[Int]] = Array(repeating: 
                         Array(repeating:MAX, count: 201),  
                           count:201)


func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    // a = a 도착지점 
    // b = b 도착지점
    // s = 출발지점
    
    for i in 1...n {
        adj[i][i] = 0
    }

    for fare in fares {
        let c = fare[0]
        let d = fare[1]
        let f = fare[2]
        adj[c][d] = f 
        adj[d][c] = f
    }
    
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                if adj[i][j] > adj[i][k] + adj[k][j] {
                    adj[i][j] = adj[i][k] + adj[k][j]
                }
            }
        }
    }   
    
    var ans: Int = Int.max
    
    for mid in 1...n {
        ans = min(ans, adj[s][mid] + adj[mid][a] + adj[mid][b])
    }
    
    return ans
}