はじめに
paiza×Qiita コラボキャンペーンの参加記事です。
このコラボキャンペーン対象問題にある「島探し」を、3通りのやり方で解いてみたので、その解説を書いていきます。
問題概要
問題の内容は難しくないので、問題文を見てもらう方がよいと思います。
大雑把に書くと、白と黒で塗られたグリッドがあるので黒色になっている塊の数を求めよ、という問題です。
大まかな解き方
黒いマスを見つけたら、そこに隣接する黒いマスを見つける、という手続きを隣接する黒いマスが無くなるまでやり続けることで、一つの島をくまなく調べることができます。
基本的には、島をくまなく調べるときの探し方の違いが解き方の違いになります。
この調べる方法として使うアルゴリズムが幅優先探索(BFS)や深さ優先探索(DFS)です。
BFS や DFS について知らない場合は以下の記事が参考になります。
幅優先探索(BFS)で解く
まずは幅優先探索を使って解いていきます。
前述したように黒いマスを見つけたら、そこから BFS を使って島全体を探索する、というようなコードを書けばよいです。
肝となるのは何度も BFS を使うという点です。
また、一度探索した黒いマスを二回以上探索しないように覚えておく必要があります。これをしないと、同じ島を何度もカウントしてしまう可能性があるためです。
以下、解答コードです。
use std::io::BufRead;
fn main() {
let stdin = std::io::stdin();
let mut stdin = stdin
.lock()
.lines()
.map(Result::unwrap)
.flat_map(|s| s.split_whitespace().map(str::to_string).collect::<Vec<_>>());
let m: usize = stdin.next().unwrap().parse().unwrap();
let n: usize = stdin.next().unwrap().parse().unwrap();
let grid = (0..n)
.map(|_| {
(0..m)
.map(|_| stdin.next().unwrap().parse::<usize>().unwrap())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
let mut ans = 0;
let mut used = vec![vec![false; m]; n];
for si in 0..n {
for sj in 0..m {
if used[si][sj] || grid[si][sj] == 0 {
continue;
}
ans += 1;
bfs(si, sj, &mut used, n, m, &grid);
}
}
println!("{}", ans);
}
const DIRECTIONS: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
fn bfs(
si: usize,
sj: usize,
used: &mut [Vec<bool>],
n: usize,
m: usize,
grid: &[Vec<usize>],
) {
let mut queue = std::collections::VecDeque::from([(si, sj)]);
used[si][sj] = true;
while let Some((i, j)) = queue.pop_front() {
for (di, dj) in DIRECTIONS {
let ni = (i as isize + di).clamp(0, n as isize - 1) as usize;
let nj = (j as isize + dj).clamp(0, m as isize - 1) as usize;
if used[ni][nj] || grid[ni][nj] == 0 {
continue;
}
queue.push_back((ni, nj));
used[ni][nj] = true;
}
}
}
コードを少しだけ解説します。
前半部分は入力なので飛ばします。
下記の部分が、
黒いマスを見つけたら、そこから BFS を使って島全体を探索する
に対応するコードです。
let mut ans = 0;
let mut used = vec![vec![false; m]; n];
for si in 0..n {
for sj in 0..m {
if used[si][sj] || grid[si][sj] == 0 {
continue;
}
ans += 1;
bfs(si, sj, &mut used, n, m, &grid);
}
}
println!("{}", ans);
左上から右下へと順にマスを見ていき、今までに探索していない黒いマスが見つかった時に、見つけた島の数を +1 して、そのマスから BFS を行うようにしています。
また bfs 関数の中で探索したマスについて覚えておけるように、可変参照で二次元配列 used を渡すようにしています。
下記の部分が BFS のコードです。
const DIRECTIONS: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
fn bfs(
si: usize,
sj: usize,
used: &mut [Vec<bool>],
n: usize,
m: usize,
grid: &[Vec<usize>],
) {
let mut queue = std::collections::VecDeque::from([(si, sj)]);
used[si][sj] = true;
while let Some((i, j)) = queue.pop_front() {
for (di, dj) in DIRECTIONS {
let ni = (i as isize + di).clamp(0, n as isize - 1) as usize;
let nj = (j as isize + dj).clamp(0, m as isize - 1) as usize;
if used[ni][nj] || grid[ni][nj] == 0 {
continue;
}
queue.push_back((ni, nj));
used[ni][nj] = true;
}
}
}
基本的な BFS が書かれているだけですが、関数に分けるにあたって可変参照を用いています。理由については先ほど書いた通りです。
また DIRECTIONS に隣接するマスの方向が格納されています。
斜めも含めて隣接すると判定する場合でも、ここに値を追加するだけの修正で解くことができます。
そして、探索範囲が表の外にはみ出るのを防ぐために clamp を使用しています。
深さ優先探索(DFS)で解く
次は深さ優先探索を使って解いていきます。
BFS を使って解いたコードと実は大きく変わりません。
fn main() {
// 入力部分は共通なので省略
let mut ans = 0;
let mut used = vec![vec![false; m]; n];
for si in 0..n {
for sj in 0..m {
if used[si][sj] || grid[si][sj] == 0 {
continue;
}
ans += 1;
dfs(si, sj, &mut used, n, m, &grid);
}
}
println!("{}", ans);
}
const DIRECTIONS: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
fn dfs(
si: usize,
sj: usize,
used: &mut [Vec<bool>],
n: usize,
m: usize,
grid: &[Vec<usize>],
) {
let mut stack = vec![(si, sj)];
used[si][sj] = true;
while let Some((i, j)) = stack.pop() {
for (di, dj) in DIRECTIONS {
let ni = (i as isize + di).clamp(0, n as isize - 1) as usize;
let nj = (j as isize + dj).clamp(0, m as isize - 1) as usize;
if used[ni][nj] || grid[ni][nj] == 0 {
continue;
}
stack.push((ni, nj));
used[ni][nj] = true;
}
}
}
実際に比較すると分かると思いますが、メイン関数の部分は bfs 関数を使うか dfs 関数を使うか、の違いしかありません。
また bfs 関数と dfs 関数の中身に関しても、キューを使っているかスタックを使っているかの違いしかありません。
なので、コードに関する説明は特にしません。
DFS を書く時は再帰を使う、という人も多いかもしれませんが、似たようなアルゴリズムであることが分かるように、敢えてスタックを使う実装にしています。
BFS と DFS の動きを見る
コードを見るだけでは物足りないと思ったので、入力例2を用いて BFS と DFS の動きをアニメーションにして比較してみます。
それぞれの色の意味は以下の通りです。
- 赤: 現在見ているマス
- 橙: キュー(スタック)に入っているマス
- 緑: 見終わったマス
白と黒の意味が問題文と反転しているので、注意してください。
| BFS | DFS |
|---|---|
 |
 |
一つ目の島での探索を見ると、同心円状に探索範囲が広がっていくのが BFS で、端っこまで行って戻るのを繰り返して探索しているのが DFS といった感じで、アルゴリズムの違いが分かると思います。
逆に、以下の部分は全く一緒であることも分かると思います。
- 探索していないマスを見つける方法・タイミング
- 探索が終わるタイミング
- 計算量 $O(NM)$
別の例
大きめの島があると分かりやすいかもしれないと思ったので、一応載せておきます。
| BFS | DFS |
|---|---|
 |
 |
発展的な解き方(素集合データ構造を用いる方法)
素集合データ構造(Disjoint Sets) と呼ばれるデータ構造を用いることでも解くことができます。
素集合データ構造の実装として有名なものに Disjoint Set Union(Union Find) と言われるものがあります。
以下のスライドを参照すると良いです。
これを用いることで、あるマスとあるマスを同じ集合にすることや、あるマスとあるマスが同じ集合に属しているかどうかの判定を、高速に行うことができます。
以下、解答コードです。
const DIRECTIONS: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
fn main() {
// 入力部分は共通なので省略
let mut ans: usize = grid.iter().flatten().sum();
let mut dsu = DisjointSetUnion::new(n * m);
for i in 0..n {
for j in 0..m {
if grid[i][j] == 0 {
continue;
}
for (di, dj) in DIRECTIONS {
let ni = (i as isize + di).clamp(0, n as isize - 1) as usize;
let nj = (j as isize + dj).clamp(0, m as isize - 1) as usize;
if grid[ni][nj] == 0 || dsu.same(m * i + j, m * ni + nj) {
continue;
}
dsu.unite(m * i + j, m * ni + nj);
ans -= 1;
}
}
}
println!("{}", ans);
}
pub struct DisjointSetUnion {
parent: Vec<usize>,
rank: Vec<usize>,
}
impl DisjointSetUnion {
pub fn new(n: usize) -> Self {
Self {
parent: (0..n).collect(),
rank: vec![0; n],
}
}
pub fn same(&mut self, a: usize, b: usize) -> bool {
self.root(a) == self.root(b)
}
pub fn unite(&mut self, a: usize, b: usize) {
let mut x = self.root(a);
let mut y = self.root(b);
if x == y {
return;
}
if self.rank[x] < self.rank[y] {
std::mem::swap(&mut x, &mut y);
}
self.parent[y] = x;
if self.rank[x] == self.rank[y] {
self.rank[y] += 1;
}
}
pub fn root(&mut self, a: usize) -> usize {
if self.parent[a] == a {
a
} else {
self.parent[a] = self.root(self.parent[a]);
self.parent[a]
}
}
}
これも軽く解説します。
ただし DisjointSetUnion の部分は、先ほど挙げたスライドの実装と殆ど同じなので、解説を省きます。
まず、答えである島の数を黒いマスの数として初期化しています。後から隣接する黒いマスを見つけるたびに、値を減らしていき、正しい値にしていきます。
二つあった島を一つに統合していくというのを繰り返すイメージです。
また DisjointSetUnion の初期化で、集合の大きさを $NM$ としています。これは全てのマスが、集合の各要素と対応付けられるようにするためです。
let mut ans: usize = grid.iter().flatten().sum();
let mut dsu = DisjointSetUnion::new(n * m);
左上から右下へとマスを見ていき、黒いマスが見つかったら、隣接する黒いマスが同じ集合に属しているかどうかを見ます。
同じ集合に属している場合は、既に見ているマスになるので、何もしません。
同じ集合に属していない場合は、同じ集合になるようにまとめます。このとき、二つの島だと思われていた物が統合されるので、答えを一つ減らします。
for i in 0..n {
for j in 0..m {
if grid[i][j] == 0 {
continue;
}
for (di, dj) in DIRECTIONS {
let ni = (i as isize + di).clamp(0, n as isize - 1) as usize;
let nj = (j as isize + dj).clamp(0, m as isize - 1) as usize;
if grid[ni][nj] == 0 || dsu.same(m * i + j, m * ni + nj) {
continue;
}
dsu.unite(m * i + j, m * ni + nj);
ans -= 1;
}
}
}
Disjoint Set Union での動きを見る
これもアニメーションにしてみました。
色と数字の意味は以下の通りです。
- 赤: 現在見ているマス
- 橙: まとめようとしているマス
- 数字: Disjoint Set Union における根の番号
白と黒の意味が問題文と反転しているので、注意してください。
根の番号が違うものを見つけるたびに、統合されて島ができあがっていく様子が分かると思います。
計算量については Disjoint Set Union の各操作の計算量 amortized $O(\alpha(NM))$ が掛けられるので $O(NM\alpha(NM))$ になります。
$\alpha(n)$ や Disjoint Set Union の計算量について知りたい場合は、以下のサイトを参照すると良いです。
BFS, DFS と Disjoint Set Union の使い分け
Disjoint Set Union は BFS, DFS と比べると、少し難しいアルゴリズムだと思うので、積極的に使う理由がないと考える人も多いと思います。
しかも Disjoint Set Union を使う方が、計算量の面でもやや劣っています。
せっかくなので Disjoint Set Union を使う方が有利になるような問題を考えてみます。
問題文
$N$ 行 $M$ 列の表と $Q$ 個のクエリが与えられます。
$i$ 番目のクエリでは $r_i$ 行 $c_i$ 列が黒いマスに変化するので、その時の島の数を求めてください。
ただし、一度黒いマスに変化したマスが元に戻ることはありません。
また、表の内容や島の定義については、元の問題と同じとします。
制約
- $1 \leq N, M \leq 10^3$
- $1 \leq Q \leq 10^5$
- $1 \leq r_i \leq N$
- $1 \leq c_i \leq M$
この問題を BFS や DFS で解こうとすると、クエリが与えられる度に BFS や DFS を実行する必要があり、かなり工夫をしなければ、制限時間に間に合いません。
しかし Disjoint Set Union で解く場合は、クエリが与えられる度に、隣接するマスのみを調べれば十分なので、制限時間内に解くことができます。
おわりに
Rust で解いて記事を書いてみよう、くらいの気持ちだったのですが、思ったより長くなってしまいました。
あと GIF 画像も Rust で作成していたので、そのライブラリを理解するのにも思ったより時間がかかってしまいました……(この辺りは Python が情報豊富で楽な気がします)