[Swift Algorithm] 72413 합승 택시 요금 (2021 카카오 블라인드)

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

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

시작지점으로부터 A, B까지 가는 택시요금의 최소합을 구하는 문제구요

A,B가 합승해서간다면 요금이 절약되기때문에 고려해야하구요

 

S->A

S->B 로 가는 최저요금을 플로이드 와샬을 이용해서

모든 지점으로부터 모든 지점까지의 최소요금을 계산해봤어요

노드 갯수 제한이 200이라서 200^3 이면 충분히 가능한 시간이죠

 

 

여기서 이제 구해야할 것은 S -> 경우지점 까지의 요금과

경우지점 -> A + 경우지점 -> B의 요금의 최소를 구하는게 문제겟죠?

 

주어진 노드를 모두 탐색하면서 비교해서 최소요금을 구할 수 있어요

(s->1) + (1->a) + (1->b)     =    시작지점에서 1번노드까지 합승하고 1->a 요금과 1->b요금을 더한 값

이 값이 최소인경우를 찾아가면되고

 

비교를 시작할 최소값은 시작지점으로부터 A, B를 가는 요금으로 합승하지않았을 경우로 지정해놓구요

 

 

여기까지는 로직이 잘 맞는것 같아요 하지만 몇몇 케이스가 오류가 나는걸 볼 수 있어요

우선 max범위를 잘 확인해야해요

n은 200개이하 

f는 100,000이하 라는 제한이 있기때문에

만약 n이 200개에 요금이전부 100,000으로 설정된 문제라면

max값이 20,000,000보다 작으면 원하는 값이 나오지 않을 문제가 있을 수 있어요

모든 경로를 통해 가면 200 * 100,000이 요금이 나올 수 있기 때문이죠

이 값을 고려해서 최댓값을 설정해주면 해결되요

 

 

또 하나의 문제로는

플로이드와샬의 시간초과에요!

분명 200^3은 여유있는 시간이긴한데 

좀 더 효율적으로 만들어보면

두번째 for문에서 현재 지점에서 갈 수 없는 지점(값이 maxValue로 설정된경우)이라면

세번째 for문으로 넘어가지않아도 될거에요

굳이 세번째 for문을 돌리지않아도 어짜피 못가는경우라 배제되거든요

 

또한 이문제에서는 자기자신은 고려하지 않기때문에 제외해줬구요

이렇게 플로이드와샬을 최적화 해주면 시간초과도 해결 되더라구요

 

 

 

풀이방법

private func solutionP72413(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    let maxValue = 20_000_000
    var arr = (0..<n).map { _ in Array(repeating: maxValue, count: n) }
    
    for fare in fares {
        let node1 = fare[0] - 1
        let node2 = fare[1] - 1
        let cost = fare[2]
        
        arr[node1][node2] = cost
        arr[node2][node1] = cost
    }
    
    func 플로이드와샬() {
        for i in 0..<n {
            for j in 0..<n {
                if arr[j][i] == maxValue || i == j {
                    continue
                }
                for k in 0..<n {
                    if j == k {
                        continue
                    }
                    arr[j][k] = min(arr[j][i] + arr[i][k], arr[j][k])
                }
            }
        }
    }
    플로이드와샬()
    var minFare = arr[s-1][a-1] + arr[s-1][b-1]
//    arr.forEach { print($0) }
    for i in 0..<n {
        let start = arr[s-1][i]
        let a = a-1 == i ? 0 : arr[i][a-1]
        let b = b-1 == i ? 0 : arr[i][b-1]
        minFare = min(minFare, start+a+b)
    }
//    print(minFare)
    return minFare
}

//solutionP72413(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]])
//solutionP72413(7, 3, 4, 1, [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]])
//solutionP72413(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]])