<Medium> Evaluate Division (LeetCode : C#)

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

📕 문제 설명

두 변수를 나눈 값들에 대한 정보가 주어진다. 다른 두 변수를 여러 개 가지는 query에 대한 나눗셈 결과를 반환하기

equations[i] = [A_i, B_i]의 값은 A_i / B_i = values[i]를 나타낸다.

• Input
  equations, values, queries
• Output
  queries 계산 결과 (정보가 없어서 계산이 안되는 경우 -1.0으로 반환)

예제

풀이

DFS 사용한 풀이
dictionary로 계산 값들 미리 저장해두고 query에 대한 값들을 계산할 수 있는 상황까지 찾아 들어간 다음 최종적으로 (num/key) * (key/den) = (num/den) 형태로 찾아내게 된다.

public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        
        HashSet<string> visited = new HashSet<string>();
        // num1 / num2 = double 형태
        Dictionary<string, Dictionary<string, double>> dict = new Dictionary<string, Dictionary<string, double>>();

        for (int i = 0; i < equations.Count; i++)
        {
            string numerator = equations[i][0];
            string denominator = equations[i][1];
            double resultValue = values[i];

            if (!dict.ContainsKey(numerator)) dict[numerator] = new Dictionary<string, double>();
            if (!dict.ContainsKey(denominator)) dict[denominator] = new Dictionary<string, double>();
            dict[numerator][denominator] = resultValue;
            dict[denominator][numerator]  = 1 / resultValue;
        }

        return queries.Select(q => EvaluateQuery(q[0], q[1], dict, visited)).ToArray();
    }

    private double EvaluateQuery(string num, string den, Dictionary<string, Dictionary<string, double>> dict, HashSet<string> visited)
    {
        if (!dict.ContainsKey(num) || !dict.ContainsKey(den)) return -1;
        if (num == den) return 1;
        if (dict.ContainsKey(num) && dict[num].ContainsKey(den)) return dict[num][den];
            
        visited.Add(num);
        double cur = -1;
        foreach (var key in dict[num].Keys) // num1 / num2 => num2들을 순회하면서 check
        {
            if (!visited.Contains(key)) // 아직 방문 x
            {
                cur = EvaluateQuery(key, den, dict, visited); // key / den 값
                if (cur != -1)
                {
                    cur = cur * dict[num][key]; // (num / key) * (key / den) = num / den
                    break;
                }
            }
        }

        visited.Remove(num);
        return cur;
    }
}

결과