[Leetcode] 2101. Detonate the Maximum Bombs

풀이

목표

• 연쇄 폭발이 이루어졌을 때 터지는 폭탄의 최대 개수

사용한 알고리즘

• DFS(Recursive)

가능한 다른 알고리즘

• DFS(Iterative)
• BFS

처음에는 연쇄 폭발의 개수가 최대인 폭탄 하나만을 골라서 개수를 구했는데 오답 처리가 됐다.
그래서, 모든 폭탄에 대해서 탐색하는 방식으로 수정했다.

1. 모든 폭탄에 대해, 연쇄 폭발 범위에 들어오는 폭탄의 번호를 저장한다(dictionary)
2. 모든 폭탄에 대해, 연쇄 폭발을 확인한다.
   • 폭탄을 탐색할 때 이미 터진 폭탄이면 확인하지 않는다.
   • 연쇄 폭발을 확인할 때도 이미 터진 폭탄이면 확인하지 않지만, 추가적으로 연쇄 폭발 범위 안에 다른 폭탄이 존재하지 않는다면(dictionary의 value의 길이가 0) 종료한다.

연쇄 폭발 범위에 들어오는지 확인은 어떻게?
원의 내부 점 판단 공식을 사용한다.
원의 중심: (a, b), 반지름: r, 외부점: (x, y) ➡️ $(x - a)^2 + (y - b)^2 <= r^2$

코드

'''
연쇄 폭발이 많이 일어나는 폭탄만 골라서 확인? [오답]
-> 모든 폭탄에 대해서 연쇄 폭발을 확인해야 한다.
'''
class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        detonated = defaultdict(list) # 특정 폭탄의 연쇄 폭발 범위 안에 존재하는 폭탄의 개수
        n = len(bombs)

        # 초기화
        for i in range(n):
            detonated[i] = []

        # 특정 폭탄의 연쇄 폭발 범위 안에 존재하는 폭탄의 개수 확인
        for i in range(n):
            x, y, r = bombs[i]
            for j in range(n):
                if i == j: continue
                sx, sy, sr = bombs[j]
                if (sx - x) ** 2 + (sy - y) ** 2 <= r ** 2: # 범위(원) 내부에 존재하는 점인지 확인
                    detonated[i].append(j)
        
        # 연쇄 폭발 확인
        def helper(index):
            flag[index] = 1 # 1: 터짐, 0: 터지지 않음
            if not detonated[index]: # 연쇄 폭발 범위 안에 다른 폭탄이 없다면 종료
                return
            for bomb in detonated[index]:
                if not flag[bomb]: # 연쇄 폭발이 일어나지 않은 폭탄인 경우에만
                    helper(bomb)
                    
        max_count = 0 # 최대 연쇄 폭발 개수

        # 모든 폭탄에 대해서 탐색
        # 연쇄 폭발이 많이 일어나는 기준으로 하면 오답
        for i in range(n):
            flag = [0] * n # 연쇄 폭발이 일어났는지 확인하는 배열
            idx, nxt = i, detonated[i] # 폭탄 번호, 연쇄 폭발 범위안에 존재하는 폭탄 배열
            
            helper(idx)

            max_count = max(max_count, flag.count(1)) # 갱신

        return max_count