AtCoder が提供しているABC（AtCoder Beginner Contest）325 のC問題をC++とPythonで解いてみました。ABC325は、2023年10月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Sensors（Difficulty : 400）
問題はリンク先をご覧ください。
連結成分の個数を求めます。DFSで解きました。AtCoder Problems による Difficulty は、400 でした。
解答案
グラフの連結成分の個数を求める問題です。
DFS（深さ優先探索：Depth-First Search）、BFS（幅優先探索：Breadth-First search）、UnionFind を使って求めることができます。この記事では、わたしが慣れている DFS で解くプログラムを紹介します。
再帰関数で DFS を実現します。グリッドの文字 ‘#’ に注目して処理をします。
- 見つけた文字 ‘#’ を ‘.’ に変更する。
- 連結している範囲内に ‘#’ を見つけたら、再帰的に処理を行う。
- この関数の処理が終わると、連結している範囲の文字 ‘#’ が ‘.’ に変更されている。
ABC269D問題（解説記事）も、連結成分の個数を求める類題となります。
C++ プログラム例（ABC325C）
左上から文字 ‘#’ を見つけたら、再帰関数を使って連結成分の文字を ‘.’ に変更します（36行目）。全体の構造としては、’#’ を見つけた回数（変数 result）が連結成分の個数となります（35、41行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int h, w;
vector<string> s;
void dfs(int i, int j)
{
s[i][j] = '.';
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if ((0 <= di + i)&&(di + i < h)&&
(0 <= dj + j)&&(dj + j < w)&&
(s[di + i][dj + j] == '#')) {
dfs(di + i, dj + j);
}
}
}
return;
}
int main()
{
cin >> h >> w;
s.resize(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int result = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
++result;
dfs(i, j);
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC325C）
Python は、関数の再帰呼び出しの回数の上限を設定しています。一般的には、1000 が設定されている環境が多いようです。関数の再帰呼び出し回数の上限を増やしました（2、4行目）。
Python の文字列は、書き換えができないため、2次元リスト f として表現して解きました。基本的な考え方は、C++ と同じです。
"""AtCoder Beginner Contest 325 C"""
import sys
sys.setrecursionlimit(1000000)
def dfs(i, j):
global h, w, f
f[i][j] = 0
for di in range(-1, 2):
for dj in range(-1, 2):
if 0 <= di + i < h and \
0 <= dj + j < w and \
f[di + i][dj + j] == 1:
dfs(di + i, dj + j)
h, w = map(int, input().split())
s = [input() for i in range(h)]
f = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
for j in range(w):
f[i][j] = 1 if s[i][j] == '#' else 0
result = 0
for i in range(h):
for j in range(w):
if f[i][j] == 1:
result += 1
dfs(i, j)
print(result)こちらも「AC」と判定されました。
最後に
連結成分の個数を求める問題は、わたしはDFSで解いています。解く手法を決めておくことでミスを減らせると考えています。
今回は、ＡからＣ問題を16:02で解くことができました。私にとってはかなり速く解けたと感じました。
引き続き ABC の問題を紹介していきます。
