🔥[99클럽 코테 스터디] 25일차 TIL - Evaluate Division

⏳문제

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.

🚨제한 사항

• 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 consist of lower case English letters and digits.

📄입출력 예

입출력 예 #1

입력

equations	values	queries
[["a","b"],["b","c"]]	[2.0,3.0]	[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

출력

output
[6.00000,0.50000,-1.00000,1.00000,-1.00000]

설명
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

---

입출력 예 #2

입력

equations	values	queries
[["a","b"],["b","c"],["bc","cd"]]	[1.5,2.5,5.0]	[["a","c"],["c","b"],["bc","cd"],["cd","bc"]]

출력

output
[3.75000,0.40000,5.00000,0.20000]

---

입출력 예 #3

입력

equations	values	queries
[["a","b"]]	[0.5]	[["a","b"],["b","a"],["a","c"],["x","y"]]

출력

output
[0.50000,2.00000,-1.00000,-1.00000]

---

✏️풀이

문제 설명만으로는 이해가 잘 안돼서 입출력 예시를 자세히 살펴보았다.

입출력 예 #1을 살펴보면,
["a","b"]의 value는 2.0
["b","c"]의 value는 3.0으로 주어졌다.

이는 아래의 두 관계가 주어졌다는 의미이다.

• a / b = 2.0
• b / c = 3.0

그리고 입력의 queries 중 ["a","c"]에 해당하는 출력으로, a / c가 나와야 한다.
이 때, a / c는 a / b와 b / c를 곱한 값으로, 6.0이 출력된다.

그렇다면 queries 중 ["b", "a"]의 출력값은 어떻게 될까?

바로 a / b의 역수인 0.5가 출력된다.

이렇게 형성된 관계를 아래의 그림과 같이 가중치 방향 그래프로 나타낼 수 있었다.

이제, 이 그래프에서 원하는 출발지와 도착지 사이의 최단 경로를 구해 경로 상에 있는 가중치를 곱해주면 원하는 출력값을 얻을 수 있다!

최단 경로 알고리즘으로는 DFS를 사용해보았다.

👾최종 코드

class Solution {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 그래프 생성
        Map<String, Map<String, Double>> graph = new HashMap<>();

        // 그래프 입력
        for (int i = 0; i < equations.size(); i++) {
            String start = equations.get(i).get(0); // 출발지
            String dest = equations.get(i).get(1); // 도착지
            double value = values[i]; // 가중치

			// 출발지가 존재하지 않으면 도착지와 가중치 입력
            graph.computeIfAbsent(start, k -> new HashMap<>()).put(dest, value);
            // 도착지가 존재하지 않으면 출발지와 가중치의 역수를 입력
            graph.computeIfAbsent(dest, k -> new HashMap<>()).put(start, 1 / value);
        }
        
        double[] answer = new double[queries.size()]; // 최종 출력 배열

        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0); // queries의 출발지 추출
            String dest = queries.get(i).get(1); // queries의 도착지 추출
            Set<String> visited = new HashSet<>(); // 방문 여부 Set 생성

            answer[i] = dfs(graph, start, dest, visited); // dfs 호출 후 반환값 저장
        }

        return answer; // 최종 결과 반환

    }
    
    // 그래프 탐색
    public double dfs(Map<String, Map<String, Double>> graph, String start, String dest, Set<String> visited) {
        if (!graph.containsKey(start)) {
            return -1.0; // 만약 출발지가 그래프에 없으면 -1 반환
        }
        if (start.equals(dest)) {
            return 1.0; // 출발지와 도착지가 같으면 1 반환
        }
        visited.add(start); // 방문 여부 표시

		// 정점에 연결된 모든 이웃 정점과 가중치를 가져옴
        for (Map.Entry<String, Double> neighbor : graph.get(start).entrySet()) {
        	// 방문하지 않았을 경우
            if (!visited.contains(neighbor.getKey())) {
            	// 현재 정점에서 도착지로 가는 경로를 찾기 위해 dfs 재귀 호출
                double result = dfs(graph, neighbor.getKey(), dest, visited);
                // 도착지에 도달한 수 있는 경로가 발견된 경우
                if (result != -1.0) {
                	// 해당 경로의 가중치에 현재 이웃 정점으로 가는 가중치를 곱하여 반환
                    return result * neighbor.getValue();
                }
            }
        }
        return -1.0; // 경로를 찾지 못했을 경우 -1.0 반환
    }
}

정점에 연결된 이웃 정점들을 탐색할 때, Map.Entry를 사용하니 Map에 저장된 모든 key-value 쌍을 각의 key-value를 가지고 있는 하나의 객체로 얻을 수 있다는 장점이 있었다.

---

🔗문제 링크
💻Repository