ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

【AtCoder版!蟻本】AGC 033 A - Darker and Darker【幅優先探索】

f:id:ebisuke33:20210318232423p:plain
AtCoder版!蟻本幅優先探索で類題としてあげられているAGC 033 AをPythonで解いていきます。

A - Darker and Darker

AtCoder Grand Contest 033 A - Darker and Darker

問題文

縦 H 行、横 W 列の白黒に塗られたマス目が与えられます。 マス目の状態は A11 から AHW の HW 個の文字で表されており、 上から i 行目、左から j 列目にあるマスが黒色のとき Aij は #、 上から i 行目、左から j 列目にあるマスが白色のとき Aij は . となっています。
すべてのマスが黒色になるまで、以下の操作を繰り返し行います。
・辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
何回の操作を行うことになるか求めてください。 ただし、最初に与えられるマス目には少なくとも 1 つ黒色のマスが存在します。

制約

・1≦H,W≦1000
・Aij は # または .
・与えられるマス目には少なくとも 1 つ黒色のマスが存在する。

解答例

from collections import deque

h, w = map(int,input().split())

A = [] # マス目の文字配列
for i in range(h):
    A.append(list(input()))

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# 白マスをすべて黒マスに変える回数を調べるbfs
def bfs():
    que = deque()
    # すべての黒マス座標をqueにいれる
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                que.append([i,j])
    # 操作回数
    res = 0

    # キューが空になるまで探索
    while True:
        num = len(que)
        while num > 0:          # 操作回数ごとの要素を取り出す
            p = que.popleft()   # 先入れのキューの要素を取り出す
            for i in range(4):  # pから4方向に移動 移動後のマス目は(nx,ny)
                ny = p[0] + dy[i]
                nx = p[1] + dx[i]
                # 隣接するマス目が範囲内で白色かの判定
                if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == ".":
                    A[ny][nx] = "#"     # 隣接する白マスを黒に置き換え
                    que.append([ny,nx]) # 隣接する白マスをqueにいれる
            num -= 1
        if len(que) == 0:
            break
        res += 1 # 操作回数を1増やす
    return res

print(bfs())

解説

H行、W列の白か黒に塗られたマス目があり、操作1回ごとに黒マスに隣接した白マスが黒マスに変わります。
すべてのマスが黒色に変わるために必要な操作回数を答える問題です。

先入れ先出しで探索できる幅優先探索の特性を活かして、探索する範囲を操作回数ごとに決めていきます。


bfs関数を呼び出すまでは基本的な幅優先探索と同じように普通に入力を受け取りました。
基本的な幅優先探索は次の記事で記載しています。
ebisuke33.hatenablog.com


bfs関数では最初に黒マスを全探索し、すべてキューに入れてしまいます。

このときキューに入っている要素が1回目の操作で探索する範囲です。


while文で幅優先探索を進めますが、len関数を用いてキューに入っている要素数だけ探索するようにしました。

例えば、while文の1回目のループでは、ループ前に全探索してキューに入っている黒マスが探索対象となります。

その探索中にキューに追加されていきますが、新しく追加された分は次回に探索することになります。

1回目のwhileを抜けると操作回数resに1を足します。


同じように2回目の操作対象は、2回目の探索時点でキューに入っている黒マスを探索し、新しくキューに追加された分は3回目に探索する、という処理を繰り返します。


最後はすべて黒マスに変わりますので、while文をbreakしてループを抜けます。

ループを抜けた後にresを出力すれば、求める操作回数となりACでした。


操作回数ごとの処理を実現するために、処理開始時点のキューの長さを覚えておくことがポイントでした。



AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com