AtCoder

ABC325 C問題(Sensors)を解く

AtCoder_ABC325_C

AtCoder が提供しているABC(AtCoder Beginner Contest)325 のC問題をC++とPythonで解いてみました。ABC325は、2023年10月21日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Sensors(Difficulty : 400)

問題はリンク先をご覧ください。

ABC325 C問題 Sensors

連結成分の個数を求めます。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で解いています。解く手法を決めておくことでミスを減らせると考えています。

今回は、AからC問題を16:02で解くことができました。私にとってはかなり速く解けたと感じました。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA