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

문제

문제 링크

설명

우선 입력으로 들어오는 equations 리스트의 각 항목에는 문자열이 들어있고, equations[i] = [a, b] 라고 하면 values 배열에는 a / b = values[i] 값이 입력으로 들어온다. 즉 b에 대한 a의 비율이 주어진다.

일단 이 문제 유형이 그래프 인지 파악하는 것부터 어렵다.. 예제를 보면 a / b = 2 이고, b / c = 3 일 때, a / c 에 대한 결과 6 을 리턴하면 되는 식이다.

이 문제 해석의 핵심은 a / b = 2 이면 b / a = 1/2 라는 것을 파악하는 것이라 생각한다. 즉 아래와 같은 방향성 있는 가중치 그래프 문제와 같다.

a  --2-->  b  --3-->  c
a <--1/2-- b <--1/3-- c 

그래프에 노드 정보만 넣어서는 안되고, 가중치 정보도 같이 넣어줘야 한다. 또한 노드 이름이 “a”, “b” 등과 같은 문자로 들어오기 때문에 인덱스로 찾는것이 불가능하다. 따라서 인접리스트 정의 시 int[][] 나, ArrayList<Integer>[] 같은 형태가 아니라 Map 의 형태로 선언해야 한다.

// {a={b=2.0}, b={a=0.5, c=3.0}, c={b=0.3333333333333333}} 와 같은 형태로 저장된다
Map<String, Map<String, Double>> graph = new HashMap<>();

풀이

public class Solution {
    // 그래프를 인접 리스트로 표현
    private Map<String, Map<String, Double>> graph = new HashMap<>();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 그래프를 구성
        buildGraph(equations, values);

        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String numerator = queries.get(i).get(0);
            String denominator = queries.get(i).get(1);
            result[i] = dfs(numerator, denominator, new HashSet<>());
        }
        return result;
    }

    private void buildGraph(List<List<String>> equations, double[] values) {
        for (int i = 0; i < equations.size(); i++) {
            String numerator = equations.get(i).get(0);
            String denominator = equations.get(i).get(1);
            double value = values[i];

            graph.putIfAbsent(numerator, new HashMap<>());
            graph.putIfAbsent(denominator, new HashMap<>());

            graph.get(numerator).put(denominator, value);
            graph.get(denominator).put(numerator, 1.0 / value);
        }
    }

    private double dfs(String current, String target, Set<String> visited) {
        if (!graph.containsKey(current) || !graph.containsKey(target)) {
            return -1.0;
        }
        if (current.equals(target)) {
            return 1.0;
        }

        visited.add(current);

        Map<String, Double> neighbors = graph.get(current);
        for (String neighbor : neighbors.keySet()) {
            if (!visited.contains(neighbor)) {
                double result = dfs(neighbor, target, visited);
                if (result != -1.0) {
                    return result * neighbors.get(neighbor);
                }
            }
        }

        return -1.0;
    }
}

회고

그래프 문제 유형을 많이 접해봐야 할 것 같다. 특히 왜 그래프 문제인지 이해하는 것이 중요하고, 그래프를 선언 시 어떤 형태로 만들 것인지도 생각해 봐야 될 것 같다.