Daily LeetCode Challenge - 399. Evaluate Division

Problem From.

https://leetcode.com/problems/evaluate-division/

오늘 문제는 equations 에 페어가 주어졌을때, values 는 그 페어를 서로 나눈 결과라고 한다. queries 에 보이는 페어에 정답이 있으면 정답을 없으면 -1.0 을 넣어서 반환하는 문제였다.

이 문제는 DFS 를 이용하여 푸는 그래프 문제였는데, a b 페어라면 a 에서 b 로 가는 비용이 2.0, 반대로 b 에서 a 로 오는 비용은 1 / 2.0 인 0.5 라는 식으로 그래프를 생각하고 풀면되는 문제였다.
a c 페어라면 a 에서 b 가 2.0, b 에서 c 가 3.0 이므로 두 수를 곱한 6.0 을 반환하게 된다. 이런식으로 그래프의 노드를 계속 탐색해나가면서 값을 곱해나가며 반환하면 된다.

class Solution {
    fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
        
        val graph = mutableMapOf<String, ArrayList<Pair<String, Double>>>()
        
        for(i in 0 until equations.size) {
            val u = equations[i][0]
            val v = equations[i][1]
            val value = values[i]

            graph.putIfAbsent(u, arrayListOf())
            graph.putIfAbsent(v, arrayListOf())

            graph[u]!!.add(Pair(v, value))
            graph[v]!!.add(Pair(u, 1 / value))
            
        }
        
        val answer = DoubleArray(queries.size)
        val num = graph.size
        
        fun dfs(src: String,dest: String,value: Double,done: MutableSet<String>
        ): Pair<Double, Boolean> {
            if (done.contains(src)) return Pair(1.0, false)
            done.add(src)
            for (node: Pair<String, Double> in graph[src]!!) {
                if (done.contains(node.first)) continue
                val newValue: Double = value * node.second
                if (node.first == dest) return Pair(newValue, true)
                val answer: Pair<Double, Boolean> = dfs(node.first, dest, newValue, done)
                if (!answer.second) continue
                return answer
            }

            return Pair(-1.0, false)
        }
        
        for (idx: Int in 0..queries.size - 1) {
            val u: String = queries[idx][0]
            val v: String = queries[idx][1]

            if (!graph.containsKey(u) || !graph.containsKey(v)) {
                answer[idx] = -1.0
                continue
            }

            if (u == v) {
                answer[idx] = 1.0
                continue
            }

            val done: MutableSet<String> = mutableSetOf()
            val temp1: Pair<Double, Boolean> = dfs(u, v, 1.0, done)
            answer[idx] = if (temp1.second) temp1.first else -1.0
        }

        return answer
    }
}