Easy-understanding || Python || Faster than 85%
Don\'t be afraid about the size of my code, I just break this down in classes and methods! What I did was converte the bombs in a graph, when the ditance betwee
Don\'t be afraid about the size of my code, I just break this down in classes and methods! What I did was converte the bombs in a graph, when the ditance between one bomb and another is smaller than the radius of the source bomb, we connect those two bombs on the graph. \n\nAfter this, we can do a DFS approach and use the visited set as the size of the bomb chain. \n\nThe biggest time complexity is the DFS algorithms that is O(V + E), where V is the number of vertices (bombs) and E is the number of edges (connected bombs).\n\n\tfrom collections import defaultdict\n\n\tclass Solution:\n\t\tdef maximumDetonation(self, bombs: List[List[int]]) -> int:\n        \n\t\t\tself.graph = self.bombs_to_graph(bombs)\n\t\t\tprint(self.graph.graph)\n\t\t\tans = 1\n\t\t\tself.dp = [0]*len(bombs)\n\t\t\tfor i in range(len(bombs)):\n\t\t\t\tvisited = set()\n\t\t\t\tself.DFS(i, visited)\n\t\t\t\tans = max(ans, len(visited))\n\t\t\treturn ans\n\n\n\n\n\t\tdef DFS(self, v, visited):\n\n\t\t\tvisited.add(v)\n\t\t\tfor neigh in self.graph.graph[v]:\n\t\t\t\tif neigh not in visited:\n\t\t\t\t\tself.DFS(neigh, visited)\n\n\t\tdef bombs_to_graph(self, bombs):\n\t\t\tgraph = Graph()\n\t\t\tfor i_s, source in enumerate(bombs):\n\t\t\t\tfor i_d, dest in enumerate(bombs):\n\t\t\t\t\tif i_s == i_d: continue\n\n\t\t\t\t\tif self.is_on_range(source, dest):\n\t\t\t\t\t\tgraph.add_edge(i_s, i_d)\n\n\t\t\treturn graph\n\n\t\tdef is_on_range(self, source, dest):\n\n\t\t\tdist = ((source[0] - dest[0])**2 + (source[1] - dest[1])**2)**0.5\n\t\t\treturn dist <= source[2]\n     \n        \n\tclass Graph:\n\t\tdef __init__(self):\n\t\t\tself.graph = defaultdict(list)\n\n\t\tdef add_edge(self, s, d):\n\t\t\tself.graph[s].append(d)
['Depth-First Search', 'Graph', 'Python', 'Python3']