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

문제 풀이

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

그래프에서 최단 경로를 구하는 “dijkstra 알고리즘”, 또는 “Floyd-Warshal 알고리즘”을 사용하면 풀 수 있는 문제입니다.

이중 플로이드 알고리즘을 사용하여서 문제를 푼다고 가정하면, 다음과 같이 모든 지점 사이의 최저 예상 택시요금을 구할 수 있습니다.

d[i][j] = i번 지점에서 j번 지점까지 갈 때의 최저 예상 택시요금

그 다음, 다음과 같이 루프를 돌면서 최솟값을 찾아주면 됩니다.

문제에서 요구하는 답 = min(d[s][k] + d[k][a] + d[k][b]) (단, k = 1 ~ n)

나의 풀이

1차 시도 (효율성 실패)

• 한 점을 중심으로 S,A,B로가는 최소비용을 dfs를 활용하여 구현하였다.

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    var result = 999999

    struct Route{
        var myNum: Int
        var neighborNum: [Int]
        var cost: [Int]
    }

    var routeArr: [Route] = []

    for i in 1...n{
        routeArr.append(Route(myNum: i, neighborNum: [], cost: []))
    }
    for i in fares{
        routeArr[i[0]-1].neighborNum.append(i[1])
        routeArr[i[0]-1].cost.append(i[2])
        routeArr[i[1]-1].neighborNum.append(i[0])
        routeArr[i[1]-1].cost.append(i[2])
    }

    var minCost = 0

    func dfs(_ start: Int, _ end: Int, _ beforeNum: [Int], _ cost: Int){
        if start == end {
            if minCost > cost {
                minCost = cost
            }
            return
        } 
        else if cost >= minCost{
            return
        }
        else {
            let route = routeArr[start-1]
            let routeCnt = route.neighborNum.count
            var cost = cost
            var beforeNum = beforeNum
            for i in 0..<routeCnt{
                if !beforeNum.contains(route.neighborNum[i]){
                    beforeNum.append(route.neighborNum[i])
                    dfs(route.neighborNum[i], end, beforeNum, cost + route.cost[i] )
                    beforeNum.removeLast()
                }
            }
        }
    }

    // 최소를 찾아야됨
    for i in 1...n{
        var costStoI = 0 // S에서 I로의 최소
        minCost = 999999
        if i != s {
            dfs(s, i, [s], costStoI)
            costStoI = minCost
        }

        var costItoA = 0 // I에서 A로의 최소
        minCost = 999999
        if i != a {
            dfs(a, i, [a], costItoA)
            costItoA = minCost
        }

        var costItoB = 0 // I에서 B로의 최소
        minCost = 999999
        if i != b {
            dfs(b, i, [b], costItoB)
            costItoB = minCost
        }

        let sum = costStoI + costItoA + costItoB
        if result > sum && sum != 0{
            result = sum
        }
    }
    
    return result
}

2차 시도 ( 참고 사이트 )

• “Floyd-Warshal 알고리즘” 활용
• 시간 복잡도 O(n^3) n이 1000일 때? 까지는 괜찮다고 한다. 문제에선 n이 최대 200까지다.

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    var result = 0
    var node: [[Int]] = []
	
    // 자기 자신은 0 그렇지 않으면 무한으로 초기화
    for i in 0...n{
        var arr: [Int] = []
        for _ in 0...n{
            arr.append(999999);
        }
        node.append(arr)
        node[i][i] = 0
    }
    
    // fares에 있는 비용으로 초기화
    for i in fares{
        node[i[0]][i[1]] = i[2]
        node[i[1]][i[0]] = i[2]
    }
    
    // Floyd-Warshal 알고리즘
    for k in 1...n{ // 거쳐가는 node
        for i in 1...n{
            for j in 1...n{
                if node[i][j] > node[i][k] + node[k][j]{ // i->j로 가는 비용과 i -> k -> j 즉, k를 거쳐가는 비용을 비교
                    node[i][j] = node[i][k] + node[k][j]
                }
            }
        }
    }
    // s에서 a + s에서 b 
    result = node[s][a] + node[s][b];
    
    for i in 1...n{
    	// s에서 i + i에서 a + i에서 b의 최소 비용을 구해준다.
        result = min(result, node[s][i] + node[i][a] + node [i][b])
    }
    
    return result
}