https://leetcode.com/problems/evaluate-division/description/
[문제]
주어진 식(equations)과 값(values)은 두 변수 간의 나눗셈 관계를 나타냅니다.
예를 들어, equations [i] = [Ai, Bi]와 values [i] = k가 주어지면, 이는 "Ai / Bi = k"를 의미합니다.
즉, Ai를 Bi로 나눈 값이 k라는 뜻입니다.
이때, queries[j] = [Cj, Dj]가 주어지면, "Cj / Dj"의 값을 계산하여 그 결과를 반환해야 합니다.
만약 해당 식을 계산할 수 없는 경우에는 -1.0을 반환합니다.
[입출력 예시]
- 입력:
- equations = [["a", "b"], ["b", "c"]]
- values = [2.0, 3.0]
- queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
- 설명:
- a / b = 2.0 (a를 b로 나눈 값은 2.0이다)
- b / c = 3.0 (b를 c로 나눈 값은 3.0이다)
- a / c = ? -> a / b * b / c = 2.0 * 3.0 = 6.0
- b / a = ? -> b / a = 1 / (a / b) = 1 / 2.0 = 0.5
- a / e = ? -> e는 주어진 변수에 없으므로, -1.0을 반환합니다.
- a / a = ? -> a를 a로 나누면 무조건 1.0입니다.
- x / x = ? -> x는 주어진 변수에 없으므로, -1.0을 반환합니다.
따라서, 최종 출력은 [6.0, 0.5, -1.0, 1.0, -1.0]이 됩니다.
[풀이]
해당 문제는 그래프 탐색 문제로 접근이 가능합니다. DFS (깊이 우선 탐색)를 활용하여 풀이를 진행했습니다.
각 Pair의 변수들은 그래프 노드로 취급하고, 변수 사이의 비율을 간선으로 간주해야 합니다.
코틀린 코드로 풀이를 진행합니다.
탐색을 위한 그리프를 먼저 생성해주어야 합니다.
// 그래프를 표현하는 자료구조
private val graph = mutableMapOf<String, MutableMap<String, Double>>()키 문자와 비율을 포함하는 Map을 Value로 취급하는 Map을 만들어줍니다.
private fun addEdge(a: String, b: String, value: Double) {
graph.computeIfAbsent(a) { mutableMapOf() }[b] = value
graph.computeIfAbsent(b) { mutableMapOf() }[a] = 1 / value
}computeIfAbsent를 활용하여 유효 값이 존재하면 반환, 없다면 기본 계산 값을 반환합니다.
이를 통해 그래프에 간선을 추가하게 됩니다.
예를 들어, a / b = 2.0이라면 그래프에는 a -> b 에는 2.0, b -> a 에는 1 / 2.0이 추가됩니다.
private fun dfs(start: String, end: String, visited: MutableSet<String>): Double {
if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0
if (start == end) return 1.0
visited.add(start)
for ((next, value) in graph[start]!!) {
if (next !in visited) {
val result = dfs(next, end, visited)
if (result != -1.0) {
return result * value
}
}
}
return -1.0
}두 변수 간 경로 탐색을 위해 DFS 함수를 구성합니다.
시작 변수에서 끝 변수까지 경로를 탐색하고 각 비율을 계산합니다.
if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0만약 그래프에서 시작 노드 또는 끝 노드가 없다면 유효하지 않은 경로이므로 바로 -1.0을 반환합니다.
if (start == end) return 1.0시작 노드와 끝 노드가 동일한 값이면 자기 자신을 의미하므로 1.0을 반환합니다.
그래프 탐색은 이미 방문한 노드인지를 확인하기 위해 visited 변수로 시작 노드를 체크해주어야 합니다.
visited.add(start) //mutableSetOf()를 초기값으로 활용
그리고 방문하지 않은 노드만을 체크하여 dfs 함수의 재귀호출을 통해 유효한 상태의 노드일 경우 비율을 반환하도록 합니다.
for ((next, value) in graph[start]!!) {
if (next !in visited) {
val result = dfs(next, end, visited)
if (result != -1.0) {
return result * value
}
}
}
이제 먼저 그래프를 생성해 주고, 생성한 그래프를 기반으로 탐색 함수를 호출해 주면 되겠습니다.
fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
// 그래프 구성
for (i in equations.indices) {
val (a, b) = equations[i]
addEdge(a, b, values[i])
}
val result = DoubleArray(queries.size)
for (i in queries.indices) {
val (a, b) = queries[i]
result[i] = dfs(a, b, mutableSetOf())
}
return result
}
전체 코드입니다.
class Solution {
private val graph = mutableMapOf<String, MutableMap<String, Double>>()
private fun addEdge(a: String, b: String, value: Double) {
graph.computeIfAbsent(a) { mutableMapOf() }[b] = value
graph.computeIfAbsent(b) { mutableMapOf() }[a] = 1 / value
}
private fun dfs(start: String, end: String, visited: MutableSet<String>): Double {
if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0
if (start == end) return 1.0
visited.add(start)
for ((next, value) in graph[start]!!) {
if (next !in visited) {
val result = dfs(next, end, visited)
if (result != -1.0) {
return result * value
}
}
}
return -1.0
}
fun calcEquation(equations: List<List<String>>, values: DoubleArray, queries: List<List<String>>): DoubleArray {
for (i in equations.indices) {
val (a, b) = equations[i]
addEdge(a, b, values[i])
}
val result = DoubleArray(queries.size)
for (i in queries.indices) {
val (a, b) = queries[i]
result[i] = dfs(a, b, mutableSetOf())
}
return result
}
}
아래는 자바 코드입니다.
import java.util.*;
class Solution {
private final Map<String, Map<String, Double>> graph = new HashMap<>();
private void addEdge(String a, String b, double value) {
graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, value);
graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / value);
}
private double dfs(String start, String end, Set<String> visited) {
if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0;
if (start.equals(end)) return 1.0;
visited.add(start);
for (Map.Entry<String, Double> entry : graph.get(start).entrySet()) {
String next = entry.getKey();
double value = entry.getValue();
if (!visited.contains(next)) {
double result = dfs(next, end, visited);
if (result != -1.0) {
return result * value;
}
}
}
return -1.0;
}
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
for (int i = 0; i < equations.size(); i++) {
List<String> equation = equations.get(i);
String a = equation.get(0);
String b = equation.get(1);
addEdge(a, b, values[i]);
}
double[] result = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
List<String> query = queries.get(i);
String a = query.get(0);
String b = query.get(1);
result[i] = dfs(a, b, new HashSet<>());
}
return result;
}
}