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

문제 설명

프로그래머스

문제를 간단히 설명하면 S 에서 A, B로가는 최단 거리를 구하는데 A, B가 같이 갈 수 있는 거리를 최대한 같이 간다음 따로따로 가게 되는 경우가 있다면 그 최단거리를 구하는 무제이다. 이를 문제에서는 길간의 거리를 요금, 같이 가는 것을 동승으로 표현했다.

출처: 프로그래머스

위의 경우는 S에서 5까지 같이 이동한뒤 (34) 5에서 B까지 (46) 5에서 A까지 (2) 가는 경우가 최단거리라고 한다. 위의 길을 준다면 총 82의 최소 거리를 출력해야 하는 문제이다.

 

문제 풀이

두가지 방법으로 문제를 풀 수 있다. 최소 경로를 구하는 다익스트라 (Dijskra) 알고리즘이나 플로이드 워셜 (Floyd-Warshall) 알고리즘으로 풀 수 있다. 노드의 갯수가 많지 않기 때문에 플로이드 워셜 알고리즘으로 충분하다.

 

플로이드 워셜 알고리즘

생각보다 코드는 아주 간단하다. 2차원 배열을 만들어서 중간노드를 거쳐가는것이 최소라면 그 값을 계속 업데이트 해주는 원리이다. 3중 for문이 들어가는 부분이 핵심이다. 마지막에 만들어진 결과로 중간을 거쳐가게 되는 경우를 고려하여 최솟값을 구한다. 여기서 중요한 것은 배열의 인덱스를 사용했기 때문에 s-1, a-1, b-1 로 생각하고 접근해야 한다는 것이다.

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    var answer = Int.max
    var distance = Array(repeating: Array(repeating: 20000000, count: n), count: n)
    
    for fare in fares {
        let i = fare[0] - 1
        let j = fare[1] - 1
        let m = fare[2]
        
        distance[i][j] = m
        distance[j][i] = m
    }
    
    for k in 0..<n {
        for i in 0..<n {
            for j in 0..<n {                
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
                distance[i][i] = 0
            }
        }
    }
        
    for i in 0..<n {
        answer = min(distance[s-1][i] + distance[i][a-1] + distance[i][b-1], answer)
    }
            
    return answer
}

이 문제는 정확성 테스트, 효율성 테스트가 있는데 둘다 문제없이 통과했다.

 

다익스트라 알고리즘

시작점을 결정해야하지만 어떻게 본다면 두 노드간의 최단거리만을 구하는 알고리즘인 다익스트라 알고리즘도 사용해보고 싶어졌다. 하지만 이는 Swift 에서 힙 구조를 지원하지 않기 때문에 직접 구현하여 사용해야 해서 코드가 길어진다는 단점이 있는데, 나는 그냥 Heap을 사용하지 않고 구현해 보았다. 추후 해결해야할 문제로 정확성 테스트는 통과했으나 효율성 테스트는 모두 통과 못했다... (따라서 아래 코드는 참고만...)

 

방식은 큐를 만들어 준 후 계속 distance를 순회하면서 최소거리를 업데이트 시켜주는 방식이다... (복잡하다... 플로이드 워셜이 좀더 접근하기 편한 것 같다)

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    var answer = Int.max
    var distance = Array(repeating: Array(repeating: Int.max, count: n), count: n)
    
    for fare in fares {
        let i = fare[0] - 1
        let j = fare[1] - 1
        let m = fare[2]
        
        distance[i][j] = m
        distance[j][i] = m
    }
    
    for i in 0..<n {
        distance[i][i] = 0
    }
    
    func dijkstra(_ s: Int) -> [Int] {
        var result = Array(repeating: 20000000, count: n)
        result[s-1] = 0
        var queue = [s-1]
        
        while !queue.isEmpty {
            let first = queue.removeFirst()
            let distances = distance[first]
            
            for (i, distance) in distances.enumerated() {
                if distance == Int.max { continue }
                if result[first] + distance < result[i] {
                    result[i] = result[first] + distance
                    queue.append(i)
                    queue.sort(by: <)
                }
            }
        }
        
        return result
    }
        
    for i in 1..<n+1 {
        answer = min(dijkstra(s)[i-1]+dijkstra(i)[a-1]+dijkstra(i)[b-1], answer)
    }
    
    return answer
}