2023-05-03

AtCoder ABC 300 C - Cross (茶色, 300 点)

AtCoder AtCoder300点茶色diff ABC-C DFS 二次元グリッド 0と1の問題連結成分連結成分ごとに分解して考える BFS Union-Find グラフ

実装が難しい系。僕は DFS をした。「島の個数」を数える問題なので、何も考えずに DFS すればいいと思った。

問題へのリンク

問題概要

下図のような $H \times W$ のグリッドの入力が与えられる。

「# で作られた x の形からなる島」が何個あるかを、島の大きさごとに答えよ。

なお、「# で作られた x の形からなる島」が互いにくっついていないことが保証されている。

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

(正確な問題文はここに)

制約

$3 \le H, W \le 100$

考えたこと

DFS など使わずに解ける賢い実装方法は公式解説にて。

僕は「グラフを連結成分ごとに分解する」という方法で解いた。まず、今回の問題をグラフだと思う方法だが、

頂点：# のあるマス
辺：斜め方向に隣接している # マス同士に辺を張る

というグラフを考えればよい。こうしてできるグラフを連結成分ごとに分解すればよい。

たとえば下図のグラフ (頂点は 0〜12 の 13 個) においては、連結成分は 3 個あり、それぞれの連結成分に含まれる頂点数は 1 個、3 個、9 個となっている。

グラフを連結成分ごとに分解するアルゴリズムとしては、

DFS (深さ優先探索)
BFS (幅優先探索)
Union-Find

の 3 つがよく知られている。いずれも、けんちょん本などで解説している。DFS, BFS については、以下の記事でも解説している。

DFS, BFS で解いた場合、計算量は $O(HW)$ となる。Union-Find で解いた場合、計算量は $O(HW\alpha(HW))$ となる。

解答例

解答例 1：DFS で解く

#include <bits/stdc++.h>
using namespace std;

// 入力
int H, W;
vector<string> C;

// 移動ベクトル
vector<int> dxs = {1, 1, -1, -1};
vector<int> dys = {1, -1, 1, -1};

// 答え
vector<int> res;

// DFS: '#' の個数を返す
// また、探索済みの `#` マスは `.` に塗りつぶすことにする
int dfs(int i, int j) {
    int res = 1;
    C[i][j] = '.';  // `.` に塗りつぶす
    for (int dir = 0; dir < 4; ++dir) {
        int ni = i + dxs[dir], nj = j + dys[dir];
        if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
        if (C[ni][nj] == '#') {
            res += dfs(ni, nj);
        }
    }
    return res;
}

int main() {
    cin >> H >> W;
    C.resize(H);
    for (int i = 0; i < H; ++i) cin >> C[i];
    
    // DFS
    int N = min(H, W);
    res.assign(N, 0);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (C[i][j] == '.') continue;
            int num = dfs(i, j);

            // レベルは '#' の個数を 4 で割った商
            res[(num / 4) - 1]++;
        }
    }
    
    // 出力
    for (int i = 0; i < N; ++i) cout << res[i] << " ";
    cout << endl;
}

解答例 2：BFS で解く

#include <bits/stdc++.h>
using namespace std;

// 入力
int H, W;
vector<string> C;

// 移動ベクトル
vector<int> dxs = {1, 1, -1, -1};
vector<int> dys = {1, -1, 1, -1};

// 答え
vector<int> res;

// BFS: '#' の個数を返す
// また、探索済みの `#` マスは `.` に塗りつぶすことにする
int bfs(int i, int j) {
    // BFS のためのデータ構造
    queue<pair<int,int>> que;
    
    // 初期条件
    que.push({i, j});
    C[i][j] = '.';
    int res = 1;
    
    // BFS 開始
    while (!que.empty()) {
        auto [x, y] = que.front();
        que.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dxs[dir], ny = y + dys[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (C[nx][ny] == '#') {
                que.push({nx, ny});
                C[nx][ny] = '.';
                ++res;
            }
        }
    }
    return res;
}

int main() {
    cin >> H >> W;
    C.resize(H);
    for (int i = 0; i < H; ++i) cin >> C[i];
    
    // DFS
    int N = min(H, W);
    res.assign(N, 0);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (C[i][j] == '.') continue;
            int num = bfs(i, j);

            // レベルは '#' の個数を 4 で割った商
            res[(num / 4) - 1]++;
        }
    }
    
    // 出力
    for (int i = 0; i < N; ++i) cout << res[i] << " ";
    cout << endl;
}

解答例 3：Union-Find で解く

#include <bits/stdc++.h>
using namespace std;

// Union-Find
struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    // 入力
    int H, W;
    cin >> H >> W;
    vector<string> C(H);
    for (int i = 0; i < H; ++i) cin >> C[i];
    
    // Union-Find
    UnionFind uf(H * W);
    
    // 隣接する '#' マスを繋いでいく
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (C[i][j] != '#') continue;
            for (int i2 = 0; i2 < H; ++i2) {
                for (int j2 = 0; j2 < W; ++j2) {
                    if (C[i2][j2] != '#') continue;
                    
                    // マス (i, j), (i2, j2) が斜めに隣接しているとき
                    if (abs(i - i2) == 1 && abs(j - j2) == 1) {
                        uf.merge(i * W + j, i2 * W + j2);
                    }
                }
            }
        }
    }
    
    // 集計
    int N = min(H, W);
    vector<int> res(N, 0);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            // 根かどうかを確認
            int id = i * W + j;
            if (uf.root(id) != id) continue;
            
            // サイズを確認
            int num = uf.size(id);
            if (num == 1) continue;  // '.' マス
            
            // レベルは '#' の個数を 4 で割った商
            res[(num / 4) - 1]++;
        }
    }
    
    // 出力
    for (int i = 0; i < N; ++i) cout << res[i] << " ";
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます