[리트코드] 399. Evaluate Division

 

문제 링크: https://leetcode.com/problems/evaluate-division/description/

 

 

문제

1. 변수 이름 2개로 이루어진 쌍 배열 `equations`와 실수값 배열 `values`가 주어진다.
    `values[i]`는 `equations[i][0] / equations[i][1]`의 값(`A/B`)을 나타낸다. 
2. 또한 변수 이름 2개로 이루어진 쌍 배열 `queries`가 주어지는데,
    각 `queries[j]`에 대해 `queries[j][0] / queries[j][1]`의 값(`C/D`)을 계산하여 결과 배열에 차례대로 저장한다.
3. 만약 값을 계산할 수 없는 경우, 해당 위치에 `-1.0`을 저장한다.

 

접근

equations = [["a","b"],["b","c"]],
values = [2.0, 3.0],
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

입력으로 주어진 `equations`과 `values`를 보면:

a / b = 2.0
b / c = 3.0

`a는 b의 2배`이고 `b는 c의 3배`라는 의미가 된다. 
결국 문제에서 원하는 건 두 변수 사이의 비율을 계산하라는 말이 된다.

 

 

그런데 `a / b = 2.0`이라면 역방향 식(역비율!)도 성립하므로 `b / a`도 알 수 있다. 그러니까 식을 뒤집어보면:

b / a = 1 / 2.0 = 0.5
c / b = 1 / 3.0 = 0.333...

그럼 원래 식과 뒤집은 식을 같이 쓰면:

a / b = 2.0
b / a = 0.5
b / c = 3.0
c / b = 1/3.0

이렇게 생각하다보면 방향 가중치 그래프를 연상하게 된다.

 

 

변수를 노드, 비율을 간선 가중치로 생각해보면:

a --(2.0)--> b -----(3.0)----> c
a <--(0.5)-- b <--(0.333...)-- c

화살표 방향은 `분모→ 분자`를 의미하게 된다. 그리고 숫자는 나눗셈 결과니까 `비율`이 된다.

 

 

이제 다시 `quries`배열로 돌아가보면, 각 쿼리는 `C/D`를 구하는 문제다. 즉 `quries[j][0]`이 출발 노드, `quries[j][1]`이 도착 노드가 된다. 그래프에서 C → D로 가는 경로를 찾으면서 지나가는 간선의 가중치를 계속해서 곱해준다.

🚧 비율은 배율의 연속 곱이다.

 

 

코드

class Solution {
	//방향 가중치 그래프 - 노드1: {노드2: 노드1/노드2}
    Map<String, Map<String, Double>> graph = new HashMap<>(); 
    double[] result;
    
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        result = new double[queries.size()];

        //각 방향에 대한 가중치 계산해서 그래프 생성
        for(int i=0; i<equations.size(); i++) {
            graph.computeIfAbsent(equations.get(i).get(0), k -> new HashMap<>()).put(equations.get(i).get(1), values[i]); // a/b
            graph.computeIfAbsent(equations.get(i).get(1), k -> new HashMap<>()).put(equations.get(i).get(0), 1.0 / values[i]); //xa
        } 

        //쿼리 계산(DFS)
        for(int i=0; i<queries.size(); i++) {
        	//C, D
            String c = queries.get(i).get(0), d = queries.get(i).get(1);
            
            //예외: 아예 그래프에 포함되지 않은 변수일 경우 불가능 
            if(!graph.containsKey(c) || !graph.containsKey(d)) result[i] = -1.0;
            
            //예외: 자기 자신에 대한 비율은 1.0
            else if (c.equals(d)) result[i] = 1.0;
            
            //무한 루프 방지용 방문 체크 세트 생성 
            else {
                Set<String> visited = new HashSet<>();
                result[i] = dfs(c, d, visited, 1.0);
            }
        }

        return result;
    }

    double dfs(String c, String d, Set<String> visited, double res) {
    	//D에 도착했으면 계산 완료했으므로 중지하고 값 리턴 
        if(c.equals(d)) return res;

        visited.add(c);
		
        //인접 노드로 이동
        for(Map.Entry<String, Double> entry : graph.get(c).entrySet()) {
            if(visited.contains(entry.getKey())) continue; //방문했으면 무시
            double num = dfs(entry.getKey(), d, visited, res * entry.getValue()); //누적곱
            if (num != -1.0) return num; //-1.0이 아니면 유효한 경로를 찾았다는 의미니까 즉시 리턴 
        }

        return -1.0;
    }
}