Python || DFS with just 3 Dimensions || Using Node Traversal Count to stop
Its mentioned that : There are at most four edges connected to each node.\nSo I have implemented a map to store how many times a node has been traversed.\nI bre
Its mentioned that : `There are at most four edges connected to each node.`\nSo I have implemented a map to store how many times a `node` has been traversed.\nI break the `dfs` process when the a node has been traversed for the `5th` time. \nThis is because **`nodes should be traversed back and forth for a max of 4 times coz it can have only 4 edges max`**\nHence the dfs gets stopped from running infinitely like `node0->node1->node0->node1.....`.\nAlso we break when the cumulatime `time` taken exceeds the `maxTime`.\nWhenever we reach node 0 , we store the total quality value `qual` so far in `sol`\n\n```py\nclass Solution:\n    def maximalPathQuality(self, quality: List[int], edges: List[List[int]], maxTime: int) -> int:\n        graph, sol = defaultdict(list), []\n        sol = []\n        for x, y, time in edges:\n            graph[x].append((y, time))\n            graph[y].append((x, time))\n\n        def dfs(node, time, qual):\n            if node == 0: sol.append(qual)\n            new_qual = qual\n            for nxt_node, nxt_time in graph[node]:\n                if time + nxt_time <= maxTime:\n                    if vis[nxt_node] + 1 >= 5: return -inf\n                    vis[nxt_node] += 1\n                    new_qual = max(dfs(nxt_node, nxt_time + time, qual + quality[nxt_node] * (vis[nxt_node] == 1)), new_qual)\n                    vis[nxt_node] -= 1\n            return new_qual\n\n        vis = defaultdict(int, {0: 1})\n        dfs(0, 0, quality[0])\n        return max(sol)\n```\n\n![image](https://assets.leetcode.com/users/images/9aed2db9-53bf-45cb-b502-db6949cc77f7_1655408346.8382185.png)\n\n\n\n\n**Happy Coding !!**\n\nIn case of any questions, feel free to ask.
['Depth-First Search', 'Python']