399. Evaluate Division

Description

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

---

399. 나눗셈계산

변수 쌍 equations 배열과 실수 values 배열이 주어집니다. 여기서 equations[i] = [Ai, Bi]와 values[i]는 방정식 Ai / Bi = values[i]를 나타냅니다. 각 Ai 또는 Bi는 단일 변수를 나타내는 문자열입니다.

또한 몇 가지 queries가 주어지며, queries[j] = [Cj, Dj]는 Cj / Dj = ?에 대한 답을 찾아야 하는 j번째 질문을 나타냅니다.

모든 질문에 대한 답을 반환하십시오. 단일 답을 결정할 수 없는 경우 -1.0을 반환합니다.

참고: 입력은 항상 유효합니다. 질문을 평가하는 과정에서 0으로 나누기가 발생하지 않으며 모순이 없다고 가정할 수 있습니다.

참고: 방정식 목록에 나타나지 않는 변수는 정의되지 않으므로, 이러한 변수에 대한 답을 결정할 수 없습니다.

예제 1:

입력: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
출력: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
설명:
주어진: a / b = 2.0, b / c = 3.0
질문은: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
반환: [6.0, 0.5, -1.0, 1.0, -1.0]
참고: x는 정의되지 않음 => -1.0

예제 2:

입력: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
출력: [3.75000,0.40000,5.00000,0.20000]

예제 3:

입력: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
출력: [0.50000,2.00000,-1.00000,-1.00000]

제약 조건:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj는 소문자 영문자와 숫자로 구성됩니다.

Solution

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;

public class Solution {
    static class Edge {
        String target; // 연결 대상 노드
        double weight; // 가중치 (변수 간 비율)

        Edge(String target, double weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 그래프를 생성하여 변수 간의 비율 관계를 나타냄
        Map<String, List<Edge>> graph = buildGraph(equations, values);

        // 쿼리 결과를 저장할 배열 초기화
        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            var src = queries.get(i).get(0);
            var dst = queries.get(i).get(1);
            Set<String> visited = new HashSet<>(); // 방문한 노드 추적
            results[i] = dfs(src, dst, visited, graph); // DFS를 사용하여 경로 계산
        }

        return results;
    }

    private Map<String, List<Edge>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, List<Edge>> graph = new HashMap<>();
        // 방정식으로부터 그래프 생성
        for (int i = 0; i < equations.size(); i++) {
            String src = equations.get(i).get(0);
            String dest = equations.get(i).get(1);
            double value = values[i];

            // 양방향 관계를 그래프에 추가
            graph.computeIfAbsent(src, k -> new ArrayList<>()).add(new Edge(dest, value));
            graph.computeIfAbsent(dest, k -> new ArrayList<>()).add(new Edge(src, 1 / value));
        }
        return graph;
    }

    private double dfs(String src, String dest, Set<String> visited, Map<String, List<Edge>> graph) {
        if (!graph.containsKey(src)) // 출발 노드가 그래프에 없으면 -1.0 반환
            return -1.0;
        if (src.equals(dest)) // 출발 노드와 도착 노드가 같으면 1.0 반환
            return 1.0;
        visited.add(src); // 현재 노드 방문 처리

        // 현재 노드에서 연결된 모든
        for (Edge edge : graph.get(src)) {
            if (visited.contains(edge.target)) {
                continue; // 이미 방문한 노드는 건너뜀
            }
            double pathValue = dfs(edge.target, dest, visited, graph); // 재귀적으로 DFS 수행
            if (pathValue != -1.0) { // 유효한 경로 발견 시
                return pathValue * edge.weight; // 현재 간선 가중치를 곱하여 결과 반환
            }
        }

        return -1.0; // 경로를 찾을 수 없는 경우 -1.0 반환
    }
}