[LeetCode] 2101번 Detonate the Maximum Bombs 문제를 풀어보았다. (ft. java)

2023년 06월 02일 금요일 - 오 6월이네..?

오늘 올려볼 문제는 2101번 Detonate the Maximum Bombs 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

아니 요즘 블로그 쓰는걸 완전 까먹어

입력

사진에서도 볼 수 있듯이 2차원 int 배열이 입력으로 들어온다.

---

풀이 및 코드

각 좌표들이 폭탄의 중심과 폭발 반경을 나타낸다.

한 폭탄을 터뜨렸을 때 최대한 많이 폭탄을 터뜨릴 수 있는 개수를 구하는 문제이다.

오늘은 조금 헤매다가 문제를 풀었다.

처음에는 union find를 사용하려고 했는데 생각해보니 union find를 하게되면 첫 번째 폭발에 연쇄되어서 폭발하는지 판별이 불가능 했다.

그래서 이후에는 dfs를 활용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int maximumDetonation(int[][] bombs) {
        var set = new HashSet<Integer>();
        int result = 0;
        
        for(int i = 0; i < bombs.length; i++) {
            if(set.contains(i)) continue;
            
            var dfsSet = dfs(bombs, new HashSet<>(), i);
            
            result = Math.max(result, dfsSet.size());
            
            for(var num : dfsSet) set.add(num);
        }
        
        return result;
    }
    
    private HashSet<Integer> dfs(int[][] bombs, HashSet<Integer> set, int now) {
        set.add(now);
        
        for(int i = 0; i < bombs.length; i++) {
            if(set.contains(i)) continue;
            
            var a = bombs[now];
            var b = bombs[i];
            
            long length = a[2], x = Math.abs(a[0] - b[0]), y = Math.abs(a[1] - b[1]);
            
            if(length * length >= x * x + y * y) dfs(bombs, set, i);
        }
        
        return set;
    }
}

---

제출 화면

시간 좀 줄여보겠다고 union find를 생각하고 거기에 얽매여서 생각보다 푸는데 오래걸렸다.

다음에는 조금 더 유연하게 생각해봐야겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.