LeetCode 2101. Detonate the Maximum Bombs
Page content
どうも、たくチャレ(@takuchalle)です。
LeetCodeの2101. Detonate the Maximum Bombsを解きました。
設問
2次元に配置された爆弾を1つだけ爆発させ、ほかの爆弾を誘発することができる。その時の爆発可能な最大爆弾数を答える問題。
解
到達可能な最大ノード数を答えるグラフ探索の問題としてとらえることで、深さ優先探索の問題として考えることができます。つまり爆弾iが誘発可能な爆弾を到達可能なノードとしてとらえます。
まず爆弾iが誘発可能な爆弾(ノード)を探します。2次元の座標と爆発の半径rが与えられているので、以下の式でそれぞれの爆弾jが誘発可能の爆弾がわかります。
$$r^2 >= (x_i - x_j)^2 + (y_i - y_j)^2$$
各爆弾から誘爆可能、つまり到達可能な爆弾のグラフが作成できます。
このグラフを用いて各爆弾を起点に爆発できる最大爆弾数を求め、その中の最大値が答えになります。
計算量はO(N^2)で、消費メモリはO(N^2)になります。
class Solution {
public:
int maximumDetonation(vector<vector<int>>& bombs) {
const auto n = bombs.size();
auto graph = vector<vector<int>>(n, vector<int>());
// 爆弾`i`から到達可能な爆弾のリストを作成する
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < n; j++) {
auto xi = bombs[i][0];
auto xj = bombs[j][0];
auto yi = bombs[i][1];
auto yj = bombs[j][1];
auto ri = bombs[i][2];
if (pow(ri, 2) >= pow(xi - xj, 2) + pow(yi - yj, 2)) {
graph[i].push_back(j);
}
}
}
int maximum = 0;
for (size_t i = 0; i < n; i++) {
auto visited = vector<bool>(n, false);
auto ret = dfs(i, graph, visited);
maximum = max(ret, maximum);
}
return maximum;
}
private:
// `node`を起点に誘発可能な爆弾数を返す
int dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
int count = 1;
visited[node] = true;
for (auto var : graph[node]) {
if (!visited[var]) {
count += dfs(var, graph, visited);
}
}
return count;
}
};
