💡 오늘의 학습 키워드
✅ 오늘 공부한 내용
👀 오늘의 회고
🤣 오늘의 문제점
- 오늘은..문제 해석부터 조금 어려웠던 것 같다!
- 어떤 방식을 써야할지 어려워서 오늘은 이미 푸신 분의 풀이를 보고 문제를 해결했다!
🔥 어떤 시도를 했는가?
변수 쌍 방정식(equations)의 배열과 실수 값(values)의 배열이 주어지며, 여기서 equations[i] = [Ai, Bi] 및 values [i]는 방정식 Ai / Bi = values [i]를 나타냅니다. 각각의 Ai 또는 Bi는 단일 변수를 나타내는 문자열입니다.
또한 몇 가지 쿼리(queries)가 제공됩니다. 여기서 queries [j] = [Cj, Dj]는 jth번째 쿼리를 나타냅니다. Cj / Dj =?에 대한 답을 찾아야 합니다.
모든 쿼리에 대한 answers를 반환합니다. 만약 답변을 확인할 수 없는 경우 -1.0을 반환합니다.
[ 노트 ]
- 입력은 항상 유효합니다. 쿼리를 평가하는 과정에서 0으로 나누는 일이 발생하지 않으며, 모순이 없다고 가정할 수 있습니다.
- 목록에 등장하지 않는 변수들은 정의되지 않으므로, 그 변수들에 대한 답은 구할 수 없습니다
• 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 는 소문자와 숫자로 구성되어 있습니다.
- test case들
- test case 1번 설명
- 주어지는 값 : 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
| 입력 equations |
values |
queries |
출력 output |
| [["a","b"], ["b","c"]] |
[2.0, 3.0] |
[["a","c"],["b',"a"],["a","e"],["a","a"],["x","x"]] |
[6.00000, 0.50000, -1.00000, 1.00000, -1.00000] |
| [["a","b"],["b","c"],["bc","cd"]] |
[1.5, 2.5, 5.0] |
[["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]] |
[3.75000, 0.40000, 5.00000, 0.2000] |
| [["a","b"]] |
[0.5] |
[["a","b"], ["b","a"], ["a","c"], ["x","y"]] |
[0.50000, 2.00000, -1.00000, -1.00000] |
- 한마디로 예제 1번을 예시로 들어보면
- a / b는 2.0, b / c는 3.0이다.
- 그럼 여기서 하나 값을 예측할 수 있는데 a / c는 a / b * b / c가 되므로 2.0 * 3.0 = 6.0이 된다.
- 반대로 b / a는 1 / 2.0 = 0.5가 된다 왜냐면 a / b를 산수로 변환시켜 풀면 되기 때문에
- a / e는 e가 주어지지 않기 때문에 - 1.0이 되고, a / a 는 자기 자신을 나누는데 값이 있기 때문에 1.0이 된다.
- x / x는 위에 나왔듯이 목록에 없기 때문에 구하지 못하니 -1.0인 것이다.
- 그래서 풀이에 대해 말해보자면 이 분은 먼저 그래프 구성을 하셨다. 각 노드로 간선 계산을 하기 위해 가중치를 주었는데 양방향의 가중치를 주기 위해 각각의 값을 아래와 같이 설정해주었다.
- graph.putIfAbsent(a, new HashMap<>()) 부분은 그래프에 a 노드가 없다면 새로 추가하기
- graph.get(a).put(b, values[i]) 부분에서는 a에서 b로 가는 간선을 추가하고 그 가중치를 values[i]로 설정
- graph.get(b).put(a, 1.0/values[i]) 부분에서는 b에서 a로 가는 간선을 추가하고 그 가중치를 1.0/values[i]로 설정했다.
for (int i = 0; i < equations.size(); i++) {
List<String> equation = equations.get(i);
String a = equation.get(0);
String b = equation.get(1);
graph.putIfAbsent(a, new HashMap<>());
graph.putIfAbsent(b, new HashMap<>());
graph.get(a).put(b, values[i]);
graph.get(b).put(a, 1.0 / values[i]);
}
- 두 번째는 DFS를 사용한 쿼리 처리를 하는데 주어진 두 변수 사이의 경로를 DFS를 통해 탐색하고 그 결과를 반환한다.
- 그리고 만약 두 변수가 연결되어 있다면 가중치를 곱해주고, 연결되어 있지 않는다면 결과로 -1.0이 된다.
- 그래서 각 쿼리에 대해서 src와 dst 두 변수 사이의 경로를 찾기 위해 DFS를 실행한다.
for (int i = 0; i < queries.size(); i++) {
List<String> query = queries.get(i);
String src = query.get(0);
String dst = query.get(1);
Set<String> visited = new HashSet<>();
results[i] = dfs(graph, src, dst, visited);
}
- 마지막은 DFS 함수에 대한 설명인데
- 재귀로 호출하고, src에서 dst로 가는 경로를 찾고, 경로를 찾으면 경로의 가중치를 곱해서 결과를 반환한다.
- 그런데 값이 존재하지 않다면 바로 -1.0을 반환하고
- 서로 같은 변수라면 1.0을 반환한다.
- 재귀로 탐색하는데 노드를 방문했다고 기록하고, 노드의 이웃들을 확인한다. 이웃 노드가 이미 방문된 노드가 아니라면 dst까지 가는 경로를 재귀적으로 탐색한다.경로가 있다면 가중치를 곱해 반환한다.
- 경로를 찾지 못한다면 -1.0을 반환한다.
private double dfs(Map<String, Map<String, Double>> graph, String src, String dst, Set<String> visited) {
if (!graph.containsKey(src) || !graph.containsKey(dst)) {
return -1.0;
}
if (src.equals(dst)) {
return 1.0;
}
visited.add(src);
Map<String, Double> neighbors = graph.get(src);
for (Map.Entry<String, Double> neighbor : neighbors.entrySet()) {
String nextNode = neighbor.getKey();
if (visited.contains(nextNode)) {
continue;
}
double result = dfs(graph, nextNode, dst, visited);
if (result != -1.0) {
return result * neighbor.getValue();
}
}
return -1.0;
}
- 보기랑 이해도 시간이 한참 걸려서 그래프에 대한 나의 이해도가 낮다고 보여졌다.. 공부를 무조건 해야할 부분인 것 같다!
- 아래는 전체 소스 코드이다! 나는 자바에서 Dare2Solve님꺼를 참고했다..!
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Map<String, Double>> graph = new HashMap<>();
// Build the graph
for (int i = 0; i < equations.size(); i++) {
List<String> equation = equations.get(i);
String a = equation.get(0);
String b = equation.get(1);
graph.putIfAbsent(a, new HashMap<>());
graph.putIfAbsent(b, new HashMap<>());
graph.get(a).put(b, values[i]);
graph.get(b).put(a, 1.0 / values[i]);
}
double[] results = new double[queries.size()];
// Helper function to perform DFS
for (int i = 0; i < queries.size(); i++) {
List<String> query = queries.get(i);
String src = query.get(0);
String dst = query.get(1);
Set<String> visited = new HashSet<>();
results[i] = dfs(graph, src, dst, visited);
}
return results;
}
private double dfs(Map<String, Map<String, Double>> graph, String src, String dst, Set<String> visited) {
if (!graph.containsKey(src) || !graph.containsKey(dst)) {
return -1.0;
}
if (src.equals(dst)) {
return 1.0;
}
visited.add(src);
Map<String, Double> neighbors = graph.get(src);
for (Map.Entry<String, Double> neighbor : neighbors.entrySet()) {
String nextNode = neighbor.getKey();
if (visited.contains(nextNode)) {
continue;
}
double result = dfs(graph, nextNode, dst, visited);
if (result != -1.0) {
return result * neighbor.getValue();
}
}
return -1.0;
}
}
👏 무엇을 새로 알았는가?
- 그래프를 푸는 전체적인 방법에 대해 공부할 수 있었던 것 같다!
👩💻 내일은 무엇을 학습할 것인가?
- 항해99문제 풀기
- 책 읽기
- 지원서 넣기
- 블로그 정리하기
