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

 

 

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

각 간선을 연결하면 곱이라는 연산으로 정의 내려질수 있고,

기존 방향과 반대 방향의 가중치는 진입 차수 배열에 1/(가중치)로 저장되면 된다.

a/b = 2 이고, b/c = 2일때, a/c == (a/b) * (b/c) 이기 때문..

 

 

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<>();
        
        // equations를 돌며 간선 정보들을 양방향으로 저장
        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 초기화
            map.putIfAbsent(end, new HashMap<>());		// 도착점의 간선 정보다 없다면 map 초기화

            map.get(start).put(end, value);	// 시작점 간선정보 - 도착점과 가중치로 put
            map.get(end).put(start, 1.0/value);	// 도착점 간선정보 - 시작점과 1.0/가중치를 put
        }
		
        // 
        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);
        }
    }
}