[LeetCode] 399. Evaluate Division

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

Evaluate Division - LeetCode

문제 유형 : DFS / BFS

문제 난이도 : Medium

 

문제

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

 

equations [ai, bi] 에서 ai / bi의 값은 values[i]이다. 제공된 queries에 대하여 각 연산값을 반환하시오 cj/dj = answer[j], 불가능하면 -1/0을 반환하시오. 0으로 나눠지는 경우는 없습니다.

 

풀이

나눗셈 값을 피제수 노드에서 제수 노드로 이동하는 비용으로 하고, 제수 노드에서 피제수 노드로 이동하는 비용으로 나눗셈 값의 역수로 한다. 이러면 그래프 순회 문제와 같아진다.

 

코드(C++)

unordered_map을 중첩하여 그래프를 만든다. {A, {B, 2.0}}과 같은 형식으로 만들 수 있다.

class Solution {
public:
    
    double dfs(const string& from, const string& to, unordered_map<string, unordered_map<string, double>>& graph, unordered_set<string>& visited) {
        if (!graph.count(from) || !graph.count(to))
            return -1.0;
        if (from == to)
            return 1.0;
        visited.insert(from);
        for (const auto& neighbor : graph[from]) {
            if (!visited.count(neighbor.first)) {
                double result = dfs(neighbor.first, to, graph, visited);
                if (result != -1.0)
                    return neighbor.second * result;
            }
        }
        return -1.0;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> graph;

        for (int i = 0; i < equations.size(); i++) {
            const string& dividend = equations[i][0];
            const string& divisor = equations[i][1];
            double value = values[i];

            graph[dividend][divisor] = value;
            graph[divisor][dividend] = 1.0 / value;
        }

        vector<double> results;
        for (const auto& query : queries) {
            const string& dividend = query[0];
            const string& divisor = query[1];
            unordered_set<string> visited;
            double result = dfs(dividend, divisor, graph, visited);
            results.push_back(result);
        }

        return results;
    }
};