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;
    }
};