[Graphs-DFS][Medium] 399. Evaluate Division

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 수식과 그 식에 해당하는 values가 함께 주어진다. 

 이때 입력된 queries에 대한 결과를 찾아 출력하라. 

 

 

Solution

  Graph 카테고리의 좋은 문제. 

  데이터의 의미를 파악할 줄 알아야 하고, 

  그래프로 이 데이터를 순회할 줄 알아야 하며, 

  대상까지의 데이터 누적과 목표산출을 복합적으로 물어보는 문제. 

 

  우선 데이터는 노드 기준으로 변환한다. 

  이때 기본 경로 값이 나눗셈이므로 그 역경로 값은 곱이 된다. 

  즉, A->B 가 2.0 이라면 B->A 는 0.5가 된다. 

  이 노드를 쿼리 시작 기준으로 순회하며 쿼리 결과 노드를 찾는다. 

  찾으면, 그때까지의 경로값의 누적 산출값을, 

  못찾으면 -1을 쿼리값으로 산출하면 되는 것이다. 

 

  위 로직을 코드로 옮겨 본다. 

 

void AddDataToNode(unordered_map<string, vector<pair<string, double>>>& mapNode, string idFrom, string idTo, double value)
{
    if (mapNode.find(idFrom) == mapNode.end())
    {
        vector<pair<string, double>> vData;
        vData.push_back(make_pair(idTo, value));

        mapNode[idFrom] = vData;
    }
    else
        mapNode[idFrom].push_back(make_pair(idTo, value));
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) 
{
    // 주어진 data를 노드기준으로 정리한다.
    unordered_map<string, vector<pair<string, double>>> mapNodes;
    for (int q = 0; q < equations.size(); ++q)
    {
        string idFrom = equations[q][0];
        string idTo = equations[q][1];

        // 정방향과 역방향을 고려하여 값을 저장한다.
        AddDataToNode(mapNodes, idFrom, idTo, values[q]);
        AddDataToNode(mapNodes, idTo, idFrom, 1.0/values[q]);
    }

    vector<double> vOut;
    for (int q = 0; q < queries.size(); ++q)
    {
        string start = queries[q][0];
        string dest = queries[q][1];
        set<string> setVisit;

        // 각 쿼리 기준으로 그래프를 순회한다.
        queue<pair<string, double>> qBuff;
        qBuff.push(make_pair(start, 1));
        double ret = -1.0;
        while (!qBuff.empty())
        {
            string cur = qBuff.front().first;
            double curValue = qBuff.front().second;
            qBuff.pop();
            if (mapNodes.find(cur) == mapNodes.end())
            {
                // 없는 경로이면 -1.0 이 쿼리의 결과.
                ret = -1.0;
                break;
            }
            if (cur == dest)
            {
                // 결과를 찾으면, 누적 경로값이 결과가 된다.
                ret = curValue;
                break;
            }
            if (setVisit.find(cur) != setVisit.end())
                continue;
            setVisit.insert(cur);

            // 곱으로 경로값을 누적한다.
            for (int z = 0; z < mapNodes[cur].size(); ++z)
                qBuff.push(make_pair(mapNodes[cur][z].first, curValue * mapNodes[cur][z].second));
        }
        vOut.push_back(ret);
    }
    return vOut;
}

 

 

결과.

 

 

Note. 문제  인지에 시간이 좀 걸렸다.  즉, 어떤 식으로 풀어야 할지 감잡는 시간이 오래 걸린다는 얘기. 

 그래프 카테고리의 더 많은 학습이 필요함을 느낀다.