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를 생각하고 거기에 얽매여서 생각보다 푸는데 오래걸렸다.
다음에는 조금 더 유연하게 생각해봐야겠다.
내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.
