Leetcode - 399. Evaluate Division

문제

["a", "b"] 데이터가 포함된 equations배열과, 같은 크기의 values 배열이 주어진다. values 의미는 각 index의 a / b를 계산한 값이다. 여기서 queries 로 전달되는 ["x", "y"] 값을 구하라.

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

해결 아이디어

• equations 으로 주어지는 데이터는 양방향 그래프로 표현될 수 있다.
• equations = [["a","b"], ...] 이고 values = [2.0, ...] 라고 할때, a -> b 의 엣지의 가중치는 2.0 그리고 b -> a 엣지의 가중치는 1/2.0 과 같다.
• 따라서 ["a", "x"]의 값은 a -> b -> .. -> x 의 과정중에 각 엣지 가중치를 곱한 결과와 동일하다.
• 흥미로운 문제였다!

해결

그래프의 자료구조를 참고하기 unordered_map<string, vector<pair<string, double>>> graph;
각 노드 string에 해당하는 노드의 인접리스트를 pair(string, double)타입 형태로 만들어서 각 노드로 향하는 가중치값고 가지게 만들었다.

class Solution {
    unordered_map<string, vector<pair<string, double>>> graph;
    unordered_map<string, bool> visited;
    vector<double> ret;
    
    void find_path(int ret_idx, string from, string tgt, double ratio) {
        if (visited[from] == true)
            return;
        if (from == tgt) {
            ret[ret_idx] = ratio;
            return;
        }
        visited[from] = true;
        for (int i = 0; i < graph[from].size(); i++) {
            find_path(ret_idx, graph[from][i].first, tgt, ratio * graph[from][i].second);
        }
        visited[from] = false;
    }

public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        ret = vector<double>(queries.size(), 0);
        /* generate a graph structure */    
        for (int i = 0; i < equations.size(); i++) {
            graph[equations[i][0]].push_back(make_pair(equations[i][1], values[i]));
            graph[equations[i][1]].push_back(make_pair(equations[i][0], 1 / values[i]));
        }
        
        for (int i = 0; i < queries.size(); i++) {
            if (graph.find(queries[i][0]) == graph.end() || graph.find(queries[i][1]) == graph.end()) {
                ret[i] = (double)-1.0;    
                continue;
            }
            find_path(i, queries[i][0], queries[i][1], 1);
            if (ret[i] == 0)
                ret[i] = (double)-1.0;    
        }
        return ret;
    }
};