# 2101. Detonate the Maximum Bombs

## :memo: Question

## :memo: 題意
* 給你 bombs list
* (x,y) 表示位置, r 表示爆炸半徑
* 請你求出最大引爆的炸彈數量？
* 炸彈可能重複放在同個位置且爆炸半徑也可能一樣, 有可能 input 長 [[1,2,3],[1,2,3],[10,2,5]]

## :memo: leetcode solution
* :medal: **思考一**: 要想出這題要用 dfs
* :medal: **思考二**: 一顆炸彈可能同時引爆所有的炸彈如果其他炸彈都在這顆炸彈的爆炸波及範圍內
* :medal: **思考三**: 是否一開始就可以用 graph 描繪出第i個炸彈會引爆哪些炸彈, 這樣就可以用 dfs 走遍所有的炸彈, 有走到就表示該炸彈會被引爆到

## :memo: my solution code

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        self.ans = 1
        # build graph
        self.graph = [[] for _ in range(len(bombs))]
        
        for i in range(len(bombs)):
            for j in range(len(bombs)):
                if i != j:
                    x, y, r = bombs[i]
                    nx, ny, _ = bombs[j]
                    
                    if (x - nx) ** 2 + (y - ny) ** 2 <= r * r:
                        self.graph[i].append(j)
        
        for k in range(len(bombs)):
            visited = set()
            visited.add(k)
            self.dfs(visited, k)
        return self.ans
    
    def dfs(self, visited, cur):
        self.ans = max(self.ans, len(visited))
        for next_bomb in self.graph[cur]:
            if next_bomb not in visited:
                visited.add(next_bomb)
                self.dfs(visited, next_bomb)
            

## :memo: BigO
* 時間複雜度: O(n^3)。
* 空間複雜度: O(n^2)。