Medium - 399. Evaluate Division

399. Evaluate Division

 

visited 변수를 dfs 생성 할때마다 생성

 

Runtime: 0ms, Beats100.00%

Memory: 16.70MB, Beats49.42%

from collections import defaultdict, deque
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:

        # 1. 그래프 생성
        adj = defaultdict(list)
        for (src, dst), val in zip(equations, values):
            adj[src].append((dst, val))  # src → dst (value)
            adj[dst].append((src, 1/val))  # dst → src (1/value)

        # 2. DFS로 경로 탐색
        def dfs(src, dst, visited):
            if src not in adj or dst not in adj: # 노드가 없으면
                return -1.0

            if src == dst: # src 와 dst 같으면, 자기자신 나누기는 1 리턴 
                return 1.0

            visited.add(src)
            for neighbor, val in adj[src]:
                if neighbor not in visited:
                    res = dfs(neighbor, dst, visited)
                    if res != -1.0:
                        return res * val # 경로를 찾았다면 값 반환
            return -1.0  # 경로를 찾지 못한 경우

        # 3. 쿼리 처리
        results = []
        for s, d in queries:
            results.append(dfs(s, d, set()))
        return results

 

visited 변수를 global 화

 

Runtime: 0ms, Beats100.00%

Memory: 16.94MB, Beats16.83%

 

from collections import defaultdict, deque
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:

        # 1. 그래프 생성
        adj = defaultdict(list)
        for (src, dst), val in zip(equations, values):
            adj[src].append((dst, val))  # src → dst (value)
            adj[dst].append((src, 1/val))  # dst → src (1/value)

        # 방문 노드 집합을 함수 외부에서 관리
        visited = set()

        # 2. DFS로 경로 탐색
        def dfs(src, dst):
            if src not in adj or dst not in adj: # 노드가 없으면
                return -1.0

            if src == dst: # src 와 dst 같으면, 자기자신 나누기는 1 리턴 
                return 1.0

            visited.add(src)
            for neighbor, val in adj[src]:
                if neighbor not in visited:
                    res = dfs(neighbor, dst)
                    if res != -1.0:
                        return res * val # 경로를 찾았다면 값 반환
            return -1.0  # 경로를 찾지 못한 경우

        # 3. 쿼리 처리
        results = []
        for s, d in queries:
            visited.clear()  # 쿼리 시작 시 방문 상태 초기화
            results.append(dfs(s, d))
        return results

 

최적화 코드

from collections import defaultdict

class Solution:
    def calcEquation(self, equations, values, queries):
        adj = defaultdict(list)

        # 그래프 생성
        for (src, dst), v in zip(equations, values):
            adj[src].append((dst, v))
            adj[dst].append((src, 1 / v))

        def dfs(src, dst, visited):
            if src not in adj or dst not in adj:
                return -1

            if src == dst:
                return 1

            visited.add(src)

            for nei, val in adj[src]:
                if nei == dst:  # 바로 목적지에 도달할 경우
            		return val
                if nei not in visited:
                    res = dfs(nei, dst, visited)
                    if res != -1:
                        return res * val

            return -1

        # 쿼리 처리
        return [dfs(s, d, set()) for s, d in queries]

 

내 코드

 

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        adj = defaultdict(list)

        for (src, dst), v in zip(equations, values):
            adj[src].append((dst, v))
            adj[dst].append((src, 1/v))

        def dfs(src, dst, visited):
            if src not in adj or dst not in adj:
                return -1
            
            if src==dst:
                return 1

            visited.add(src) # "a"
                        
            for nei, val in adj[src]:
                if nei == dst:  # 바로 목적지에 도달할 경우
                    return val
                # nei: "c"
                if nei not in visited:  # 바로 src -> dst 가 아니면
                    res = dfs(nei, dst, visited) # dfs("c", "b")

                    if res != -1: # 없는게 아니면
                        return res * val
            
            # 못 찾으면
            return -1

        res = []
        for s, d in queries:
            res.append(dfs(s,d, set()))         
        return res