99클럽 코테 스터디 25일차 TIL - [LeetCode] Evaluate Division (Java)

📌 오늘의 학습 키워드

[LeetCode] Evaluate Division (Java)
https://leetcode.com/problems/evaluate-division/description/

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : equations[], values[], queries[]
출력 : 모든 queries에 대한 답의 배열. 단, 답을 결정할 수 없는 경우 -1.0 반환

가능한 시간복잡도

O(V+E)

알고리즘 선택

그래프, dfs

📌 코드 설계하기

1. graph라는 이름의 Map<String, List>을 사용하여 그래프를 구성한다. 여기서 Node는 연결된 변수(key)와 그 변수로 가는 간선의 가중치(value)를 나타낸다.
2. equations 리스트를 순회하면서 각 방정식의 변수 var1, var2를 각각 그래프의 노드로 추가합니다.
3. var1 -> var2로 가는 간선은 주어진 값(value)을 사용하고, 반대로 var2 -> var1로 가는 간선은 1.0 / value를 가중치로 해 양방향 그래프를 형성한다.
4. 각 쿼리에 대해, 쿼리의 두 변수(var1, var2)가 그래프에 존재하는지 확인한다.
5. 두변수가 그래프에 없다면 그 쿼리의 결과는 -1.0이고, 두 변수가 그래프에 존재한다면, dfs 메소드를 호출해 var1에서 var2까지의 경로를 찾고, 그 경로의 곱셈 결과를 반환한다. 또한,visited 집합을 사용하여 방문한 노드를 추적하고, 무한 루프를 방지한다.
6. dfs 메소드는 재귀적으로 호출되며, 현재 경로에서 start에서 end로 가는 경로를 찾는다.
7. start와 end가 동일하면 현재까지의 곱(product)을 반환하고, 그렇지 않으면, start에서 연결된 모든 이웃 노드를 방문해 방문하지 않은 노드에 대해 재귀적으로 dfs를 호출한다.
8. 만약 경로를 찾으면 그 결과를 반환하고, 찾지 못하면 -1.0을 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    class Node {
        String key;
        double value;

        Node(String key, double value) {
            this.key = key;
            this.value = value;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, List<Node>> graph = new HashMap<>();
        
        // 그래프 구축
        for (int i = 0; i < equations.size(); i++) {
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);
            double value = values[i];
            
            graph.putIfAbsent(var1, new ArrayList<>());
            graph.putIfAbsent(var2, new ArrayList<>());
            
            graph.get(var1).add(new Node(var2, value));
            graph.get(var2).add(new Node(var1, 1.0 / value));
        }

        // 쿼리 처리
        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);
            
            if (!graph.containsKey(var1) || !graph.containsKey(var2)) {
                results[i] = -1.0;
            } else {
                Set<String> visited = new HashSet<>();
                results[i] = dfs(graph, var1, var2, 1.0, visited);
            }
        }
        
        return results;
    }

    private double dfs(Map<String, List<Node>> graph, String start, String end, double product, Set<String> visited) {
        if (start.equals(end)) {
            return product;
        }
        
        visited.add(start);
        
        for (Node neighbor : graph.get(start)) {
            if (!visited.contains(neighbor.key)) {
                double result = dfs(graph, neighbor.key, end, product * neighbor.value, visited);
                if (result != -1.0) {
                    return result;
                }
            }
        }
        
        return -1.0;
    }
}