Leet code (Medium) : 399. Evaluate Division (DFS) - JAVA

 

 

이 문제도 방향성이 있는 그래프 문제와 다름이 없다. 노드간 방향성이 있는 그래프로 그려보면..

각 방향은 곱으로 이어질수 있고, 기존 방향과 반대 방향의 가중치는 진입 차수 배열에 1/(가중치)로 저장되면 된다. 

 

 

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] finalAns = new double[queries.size()];
        HashMap<String, HashMap<String, Double>> map = new HashMap<>();
        
        for(int i = 0; i < equations.size(); i++){
            String start = equations.get(i).get(0);
            String end = equations.get(i).get(1);
            double value = values[i];

            map.putIfAbsent(start, new HashMap<>());
            map.putIfAbsent(end, new HashMap<>());

            map.get(start).put(end, value);
            map.get(end).put(start, 1.0/value);
        }

        for(int i = 0; i < queries.size(); i++){
            String node = queries.get(i).get(0);
            String des = queries.get(i).get(1);
            
            // equations에 값이 없는 것들은 -1 리턴
            if(!map.containsKey(node) || !map.containsKey(des)){
                finalAns[i] = -1.0;
            } else{
                // 값이 있으면 시작부터 끝까지 값을 찾음 dfs
                HashSet<String> vis = new HashSet<>();
                double[] ans = {-1.0};  // temp값의 변화를 담는 배열
                double temp = 1.0;  // 계속 값을 곱할 변수
                dfs(node, des, map, vis, ans, temp);
                finalAns[i] = ans[0];
            }
        }

        return finalAns;
    }

    public void dfs(String node, String des, HashMap<String, HashMap<String, Double>> map, HashSet<String> vis, double[]ans, double temp){
        // 이미 방문한 노드라면
        if(vis.contains(node))
            return;

        // 방문 체크
        vis.add(node);

        // 현재 노드가 목적지랑 같으면 지금 까지 곱해진 값(temp)을 리턴
        if(node.equals(des)){
            ans[0] = temp;
            return;
        }

        // 노드와 연결된 다음 노드들을 돈다.
        for(Map.Entry<String, Double> entry: map.get(node).entrySet()){
            String next = entry.getKey();
            double val = entry.getValue();
            dfs(next, des, map, vis, ans, temp * val);
        }
    }
}