初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #7 ( 幅優先探索(BFS)編 )

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います!

精選100問って何?

記事はこちら!
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今回は第7回目の幅優先探索!!

過去の記事についてはこちら!!

全探索シリーズ

第1回:全列挙

ryusuke920.hatenablog.jp

第2回:工夫して通り数を減らす全列挙

ryusuke920.hatenablog.jp

第3回:ビット全探索

ryusuke920.hatenablog.jp

第4回:順列全探索

ryusuke920.hatenablog.jp

二分探索

幅優先探索

幅優先探索の分野は全部で6問あるので、紹介したいと思います!

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja

この問題は「The 最初の問題」という感じがしました。
方針としては頂点0からスタートして、行ける場合には今いる頂点 +1 にして解いていきます。
すると、その頂点までの最小値が記録されていきます!

from collections import deque
n = int(input())
graph = [[] for _ in range(n)] # 隣接リスト
for i in range(n):
    a = list(map(int,input().split()))
    for j in range(a[1]):
        graph[a[0] - 1].append(a[j + 2] - 1)

dist = [-1] * n
dist[0] = 0 # 頂点0→0の距離は当然0
q = deque()
q.append(0)
while q:
    v = q.popleft()
    for i in graph[v]:
        if dist[i] == -1: # まだ行ってない所であれば今いる頂点 + 1をした距離が最小値となる
            dist[i] = dist[v] + 1
            q.append(i) # qに距離を記録した頂点を追加する

for i in range(n):
    print(i + 1, dist[i])

29. C - 幅優先探索

https://atcoder.jp/contests/abc007/tasks/abc007_3

この問題はAtCoderの中でもとても有名な問題ですね。
これがスラスラ書けるようになると、アルゴリズムの視野がとても広くなる気がします。

方針は至って単純で今いる場所から4方向に向かって行けるかどうかを判定する。
行ける場合には今いるマス +1 をしてあげることで判別することができます。

最近のAtCoderはこのようなアルゴリズムの問題があまり出題されてないので近い時期に出そうですね!!

from collections import deque
r, c = map(int,input().split())
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())
(sy, sx, gy, gx) = (sy - 1, sx - 1, gy - 1, gx - 1) # 0indexで設定する
grid = [[] for _ in range(r)] # r * cのgridマスを用意する
for i in range(r):
    C = list(input())
    for j in range(c):
        grid[i] = C

dist = [[10000] * c for _ in range(r)] # 各マスの最小距離を記録する2次元配列
for i in range(r):
    for j in range(c):
        if grid[i][j] == "#": # gridマスが # になっている場合は通れないので便宜上 -1 とする
            dist[i][j] = -1
dist[sy][sx] = 0 # スタート地点は0距離で行ける

q = deque()
q.append([sy, sx]) # (スタートのy座標, スタートのx座標)
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 4方向への変化量

while q:
    v = q.popleft() # (今いるy座標, 今いるx座標)
    for i, j in d: # 変化量を足していく(配列の長さである4回分)
        if not (0 <= v[0] + i <= r - 1 and 0 <= v[1] + j <= c - 1): continue # 変化量を足した際に配列外になる場合は調べない
        if grid[v[0] + i][v[1] + j] == "#": continue # マスが通れない場合は当然調べない
        if dist[v[0] + i][v[1] + j] != 10000: continue # 10000でなければ既に調べたか行けない場所なので調べない
        dist[v[0] + i][v[1] + j] = dist[v[0]][v[1]] + 1
        q.append([v[0] + i, v[1] + j]) # 次に行く場所をdequeに追加する

print(dist[gy][gx]) # ゴールのマスを出力してAC!!

30. E - チーズ (Cheese)

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_e

これは難しかった!!
しかししばらく考えてみると意外と単純で、上記で解いた問題はスタートとゴールが決まった1カ所でしたが、この問題はそれがn回出てくるだけです。
なのでfor文をn回してBFSをすればAC出来ます!!

from collections import deque
h, w, n = map(int,input().split()) # gridマスの縦、横、チーズの数
grid = [[] for _ in range(h)]
for i in range(h):
    S = list(input())
    grid[i] = S

num = [str(i + 1) for i in range(n)] # チーズを探す際に作っておくと楽になる
q = deque() # (y, x)
cheese = [[0, 0] for _ in range(n)] # それぞれのチーズのある場所を記録する配列(y座標・x座標)
for i in range(h):
    for j in range(w):
        for k in range(n):
            if grid[i][j] == num[k]:
                (cheese[k][0], cheese[k][1]) = (i, j) # それぞれの番号(チーズ)がある場所を記録する
        if grid[i][j] == "S": # スタート地点をdequeに追加する
            q.append([i, j])

d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 4方向への変化量
ans = 0 # 距離を足していくもの(いわゆる答え)
for k in range(n): # n回分チーズを食べる
    if k != 0: # i == 0 のときは既に16, 17行目でdequeに追加している
        q = deque() # (y, x)
        q.append([cheese[k - 1][0], cheese[k - 1][1]]) # n回ごとのスタート地点を決める
    dist = [[10000] * w for _ in range(h)] # boolの役割もしている
    dist[q[0][0]][q[0][1]] = 0 # スタート地点は0距離
    while q:
        v = q.popleft()
        for i, j in d:
            if not (0 <= v[0] + i <= h - 1 and 0 <= v[1] + j <= w - 1): continue # 行く先が範囲外なら調べない
            if grid[v[0] + i][v[1] + j] == "X": continue # 障害物の場合は調べない
            if dist[v[0] + i][v[1] + j] != 10000: continue # 既に調べている場所は調べない
            q.append([v[0] + i, v[1] + j]) # 次の場所をdequeに追加する
            dist[v[0] + i][v[1] + j] = dist[v[0]][v[1]] + 1 # 1歩先の場所は今いる場所から +1 して更新する
            if grid[v[0] + i][v[1] + j] == str(k + 1): # ゴール地点が見つかったらwhile文を脱出
                ans += dist[v[0] + i][v[1] + j] # スタートからゴールまでかかった分を足す
                break
print(ans)

31. E - イルミネーション (Illumination)

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_e

これは今回の6問の中では圧倒的に最難関の問題でした。
何が難しいかって、みたらわかるように4方向ではなく6方向なんですよね。
なので普通にBFSをしてもACは出来ません。

そこで各マスが装飾しなきゃいけないマスといくつ隣接してるかを数えます。
例えば、あるマスの周囲6カ所のうち2カ所に装飾すべき建物があるとします。そうすると、そこは塗らなくても良いので +4 色ぬりをします。

具体的にはTwitterでコメントいただいた下記のような画像が参考になると思います。

このような図が浮かべば、あとは偶数行・奇数行かのいずれかで場合分けをしてそれぞれの場合でBFSを行うとACすることが出来ます!

from collections import deque
w, h = map(int,input().split())
grid = [['0'] * (w + 2) for _ in range(h + 2)]

for i in range(h):
    S = list(input())
    for j in range(w):
        grid[i + 1][j + 1] = S[2 * j] # 文字列で取ってるので ' ' も含まれるから 2 * j とする

check = [[-1] * (w + 2) for _ in range(h + 2)]
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 行けるかどうかチェックする際に使用する4方向の変化量
q = deque()
q.append([0, 0])
check[0][0] = 0

odd_d = [[-1, 0], [0, -1], [1, 0], [1, 1], [0, 1], [-1, 1]] # 奇数行6近傍の変化量 (y, x)
even_d = [[-1, -1], [0, -1], [1, -1], [1, 0], [0, 1], [-1, 0]] # 偶数行6近傍の変化量 (y, x)

# BFSで行ける場所を調べ上げる(-1 = 行けない, 0 = 行ける)
while q:
    v = q.popleft()
    if v[0] % 2 == 0:
        for i, j in even_d: # (dy, dx)
            if not (0 <= v[0] + i <= h + 1 and 0 <= v[1] + j <= w + 1): continue # 範囲外は調べない
            if grid[v[0] + i][v[1] + j] == '1': continue # 行く先が建物である場合には調べない
            if check[v[0] + i][v[1] + j] != -1: continue # 既にチェック済みの場所は調べない
            q.append([v[0] + i, v[1] + j])
            check[v[0] + i][v[1] + j] = 0
    else: # v[0] % 2 == 1:
        for i, j in odd_d: # (dy, dx)
            if not (0 <= v[0] + i <= h + 1 and 0 <= v[1] + j <= w + 1): continue # 範囲外は調べない
            if grid[v[0] + i][v[1] + j] == '1': continue # 行く先が建物である場合には調べない
            if check[v[0] + i][v[1] + j] != -1: continue # 既にチェック済みの場所は調べない
            q.append([v[0] + i, v[1] + j])
            check[v[0] + i][v[1] + j] = 0

# 周囲全てが黒で覆われているものは1に書き換える(入力例1だと (3, 2) など)
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if check[i][j] == -1: # checkが -1 であれば全ての周囲が建物であるので'1'に置き換える
            grid[i][j] = '1'

ans = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] == '1': # 今いるマスが建物であれば計算を開始する
            cnt = 0
            if i % 2 == 0: # 偶数行のとき(even_dを使うとき)
                for k in range(6):
                    if grid[i + even_d[k][0]][j + even_d[k][1]] == '1':
                        cnt += 1
            else: # 奇数行のとき(odd_dを使うとき)
                for k in range(6):
                    if grid[i + odd_d[k][0]][j + odd_d[k][1]] == '1':
                        cnt += 1
            ans += 6 - cnt # 6箇所のうち建物である場所を引けば装飾するべき場所が求まる

print(ans)

32. Amazing Mazes

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp

こちらも少し癖のある問題です。
先ほどまでの問題はグリッドのマス自体に障害物がありましたが、この問題は線が障害物となっているのでそう簡単には解けません。

方針としては、調べようとしている先が縦方向なのか横方向なのかを場合分けしてそれに応じて作った障害物の有無を記載してる配列と照らし合わせて、行けるなら進み、行けない場合は止まります。
そうすると、上手くBFSを実装することができます。

コメントアウトは丁寧にしてあるので詳しくはACしたコードをみていただければわかると思います。

from collections import deque
while True:
    w, h = map(int,input().split())
    if (w, h) == (0, 0):
        exit()
    x = [[0] * w for _ in range(h - 1)] # 横線の障害物(0 = 何もない, 1 = 壁あり)
    y = [[0] * (w - 1) for _ in range(h)] # 縦線の障害物(0 = 何もない, 1 = 壁あり)

    for i in range(2 * h - 1): # 入力を受け取る
        S = list(map(int,input().split()))
        if i % 2 == 0: # 縦線の有無
            for j in range(w - 1):
                y[i // 2][j] = S[j]
        else: # 横線の有無
            for j in range(w):
                x[i // 2][j] = S[j]

    dist = [[10000] * w for _ in range(h)] # 初期値は10000で設定(boolの役割も果たせる)
    dist[0][0] = 1 # スター地点は距離1でいける
    q = deque()
    q.append([0, 0]) # スタート地点は左上の[0, 0](y・x)
    d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 4方向に対する変化量
    while q:
        v = q.popleft()
        for dy, dx in d:
            if not (0 <= v[0] + dy <= h - 1 and 0 <= v[1] + dx <= w - 1): continue # 範囲外であれば調べない
            if dist[v[0] + dy][v[1] + dx] != 10000: continue # 既にチェック済みの場所は調べない
            if dx == 0: #今調べてるのが縦(y)方向に行けるかどうかの場合
                if dy >= 0:
                    if x[v[0]][v[1]] == 1: continue # 壁のときは行けないので調べない
                else:
                    if x[v[0] + dy][v[1]] == 1: continue # 壁のときは行けないので調べない
                dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1 # 今いる場所 +1 する
                q.append([v[0] + dy, v[1] + dx]) # 新たに行けた場所をdequeに追加する               
            else: #今調べてるのが横(x)方向に行けるかどうかの場合
                if dx >= 0:
                    if y[v[0]][v[1]] == 1: continue # 壁のときは行けないので調べない
                else:
                    if y[v[0]][v[1] + dx] == 1: continue # 壁のときは行けないので調べない
                dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1 # 今いる場所 +1 する
                q.append([v[0] + dy, v[1] + dx]) # 新たに行けた場所をdequeに追加する

    if dist[-1][-1] == 10000: # 更新されてない場合は行けないことを意味している
        print(0)
    else:
        print(dist[-1][-1])

33. D - Grid Repainting

https://atcoder.jp/contests/abc088/tasks/abc088_d

本日最後の問題はこちら!!
最後だからといって難しいわけではなく、むしろ前の2問に比べたら簡単です。
必ずゴールまでの最短経路は白色でなければいけません。
なので、言い換えると最短経路以外の部分は白から黒に塗り替えても良いということになります。
それがわかれば基本問題の難易度と全く変わりません。

from collections import deque
h, w = map(int,input().split())
s = [[] for _ in range(h)]
for i in range(h):
    S = list(input())
    for j in range(w):
        s[i].append(S[j])

# マス全体の白いマスの個数を計算する
white = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white += 1

dist = [[10000] * w for _ in range(h)] # 各マスの距離を記録する配列
q = deque()
q.append([0, 0]) # スタート地点は(0(x座標), 0(y座標))
dist[0][0] = 1 # スタート地点は白いので +1 しておく
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 4方向に対する変化量
while q:
    v = q.popleft()
    for i, j in d:
        if not (0 <= v[0] + i <= h - 1 and 0 <= v[1] + j <= w - 1): continue # 行く先が範囲外なら調べない
        if s[v[0] + i][v[1] + j] == "#": continue # 黒の場合は調べない
        if dist[v[0] + i][v[1] + j] != 10000: continue # 既に調べている場所は調べない
        q.append([v[0] + i, v[1] + j]) # 新しく行く場所をdequeに追加する
        dist[v[0] + i][v[1] + j] = dist[v[0]][v[1]] + 1

last = dist[-1][-1]
if dist[-1][-1] == 10000: # 距離が更新されていないのでたどり着けない
    print(-1)
else:
    print(white - last) # 解 = (全体の白色の個数) - (通らなければならない白い場所)

最後に

意外と早く終わらせることができました!!
DFSとBFSを両方終わらせてみての感想ですが、どちらも書き方自体はとても似ている気がします。なのでDFSをある程度理解できていれば書きやすいと思います。
次回からはDPで全く分野が変わります。案の定DPについてはまだ何も知らないので時間がかかると思いますが、応援よろしくお願いします!!
それではまたいつか会いましょう!!

コードの指摘事項・アドバイス等ありましたら、コメントにてお知らせください。