99클럽 코테 스터디 25일차 TIL + 그래프

[오늘의 학습 키워드 및 문제]
- 리트코드의 "Evaluate Division" 문제를 풀었다.
- 오늘도 그래프 문제가 나왔다.

[나의 코드]

# BFS 풀이

from collections import deque

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = {}
        for i in range(len(equations)):
            x, y = equations[i][0], equations[i][1]
            
            if x not in graph:
                graph[x] = {}
            if y not in graph:
                graph[y] = {}
            graph[x][y] = values[i]
            graph[y][x] = 1 / values[i]
    
        def bfs(x, y):
            if x not in graph or y not in graph:
                return -1.0
            if x == y:
                return 1.0
            
            q = deque([(x, 1.0)])
            visited = set()
            
            while q:
                current, c_value = q.popleft()

                if current == y:
                    return c_value
                
                visited.add(current)

                for key, value in graph[current].items():
                    if key not in visited:
                        q.append((key, c_value * value))
            
            return -1.0

        result = []
        for query in queries:
            result.append(bfs(query[0], query[1]))
        
        return result

문제를 읽고 나서 딕셔너리에 키와 값을 계산해서 넣어야겠다고 생각했다.

# 예제
equations = [["a", "b"], ["b", "c"]]
values = [2.0, 3.0]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]

# 딕셔너리에 값을 넣으면 다음과 같은 그래프 형태가 만들어진다.
a --(2.0)--> b
b --(3.0)--> c

{'a': {'b': 2.0}, 'b': {'a': 0.5, 'c': 3.0}, 'c': {'b': 0.3333333333333333}}

그 다음으로는 DFS나 BFS로 탐색하면서 queries 배열에 해당하는 값을 찾아주면 된다.
근데 나는 BFS가 더 편해서 BFS로 풀었다.

q = deque([(x, 1.0)])

1.0으로 초기화한 이유는 경로의 값을 곱해가며 최종 결과를 계산해야 하는데, 0.0이면 언제나 0이기 때문이다.
그리고 자기에서 자신으로의 경로는 당연히 값이 1.0이다.

a / c = (a / b) × (b / c) = 2.0 × 3.0 = 6.0

위의 식을 보면 c_value * value 왜 이 식이 나오는지 알 수 있다.

visited가 필요한 이유는 무한 루프를 방지하기 위함이다.
a에도 b가 연결돼 있고, b에도 a가 연결돼 있는데, 중복을 허용하면 무한 참조가 일어난다.

 

# DFS 풀이

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = {}
        
        for i in range(len(equations)):
            x, y = equations[i][0], equations[i][1]
            
            if x not in graph:
                graph[x] = {}
            if y not in graph:
                graph[y] = {}
            graph[x][y] = values[i]
            graph[y][x] = 1 / values[i]
        
        def dfs(x, y, visited):
            if x not in graph or y not in graph:
                return -1.0
            if x == y:
                return 1.0
            
            visited.add(x)
            
            for key, value in graph[x].items():
                if key in visited:
                    continue
                visited.add(key)
                
                result = dfs(key, y, visited)
                
                if result != -1:
                    return value * result
            
            return -1.0
        
        results = []
        for query in queries:
            resulst.append(dfs(query[0], query[1], set()))
        
        return results

이건 DFS로 풀어본 것이다. 그냥 참고용.
똑같은 탐색인데 DFS가 왜 더 어려운 것이냐.

[오늘의 회고]
- 딕셔너리를 이중으로 구현해 본 건 오늘이 처음인데, 다른 예제도 풀어봐야겠다.
- 나도 물놀이 가고 싶다. 끝!