프로그래머스 - 합승 택시 요금 (Kotlin)

프로그래머스 level3 - 합승 택시 요금

프로그래머스

 

문제

지점의 개수 n, 출발지점을 나타내는 S , A 의 도착지점을 나타내는 A, B 의 도착지점을 나타내는 B, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다.

이때, A , B 두 사람이 S 에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.

 

만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

 

---

해설

이번 문제는 플로이드-워셜 또는 다익스트라 알고리즘을 이용하여 해결해야 한다.

이번 문제는 다익스트라를 이용하여 풀었다.

 

이 문제를 해결하기 위해서 3번의 다익스트라 알고리즘을 실행하였다.

1. S 지점에서의 최단 거리
2. A 지점에서의 최단 거리
3. B 지점에서의 최단 거리

총 3번의 다익스트라를 실행한 후 전체 노드를 for문을 이용하여 탐색해야 한다.

 

for(i in 1..n){
    if(s == i)
        continue

    ans = minOf(ans, dDist[i] + aDist[i] + bDist[i])
}

 

여기서 i 지점을 지날 때 즉, 합승 지점을 지정하고 그 지점에서의 최단 거리를 구하고 나서 제출하면 된다.

 

---

전체 코드

import java.util.*

class TaxiFee {
    private lateinit var graph: Array<MutableList<Node>>
    private var size = 0
    private data class Node(val node: Int, val cost: Int) : Comparable<Node> {
        override fun compareTo(other: Node): Int = cost - other.cost
    }
    fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
        var ans: Int = Int.MAX_VALUE
        size = n
        graph = Array<MutableList<Node>>(n + 1){ mutableListOf() }
        graph[0].add(Node(0, 0))

        fares.forEach {
            graph[it[0]].add(Node(it[1], it[2]))
            graph[it[1]].add(Node(it[0], it[2]))
        }

        val dDist = dijkstra(s)
        val aDist = dijkstra(a)
        val bDist = dijkstra(b)

        for(i in 1..n){
            if(s == i)
                continue

            ans = minOf(ans, dDist[i] + aDist[i] + bDist[i])
        }

        return ans
    }

    private fun dijkstra(s: Int): Array<Int>{
        var dist: Array<Int> = Array(size + 1){ Int.MAX_VALUE }
        val q: PriorityQueue<Node> = PriorityQueue()

        q.offer(Node(s, 0))
        dist[s] = 0

        while(q.isNotEmpty()){
            val (cNode, cCost) = q.poll()

            if(dist[cNode] < cCost)
                continue

            graph[cNode].forEach {
                val nNode = it.node
                val nCost = it.cost + cCost

                if(nCost < dist[nNode]){
                    dist[nNode] = nCost
                    q.offer(Node(nNode, nCost))
                }
            }
        }

        return dist
    }
}

 

다익스트라 알고리즘을 이용하여 해결하긴 했지만, 플로이드-워셜 알고리즘을 이용하여 해결할 수 있다는 사실도 알게 되었다.

플로이드-워셜 알고리즘도 이용하여 문제를 풀어 봐야겠다...