bfs(breadth-first search)

date: 2021-04-18 excerpt: bfs(breadth-first search)について

bfs(breadth-first search)について

幅優先探索のこと
dfsが発見したノードから探索を行うのに比べて、発見を時系列順で探索する
- bfsの性質を利用すると最も近い経路の探索が可能である
注意;
- ネットワークをstrで表現するとpypyだと非常に遅いので別途intで表現する必要がある
少し改良することで0-1 bfsと呼ばれるコストが01で表現される際のネットワークでも最小コストを求めることができる
- bfsは通常、FIFOであるが、コストがある経路のみをFILOにすることでなるべく通らずに到達可能な経路を探索することができる
ネットワークの辺の色の塗り分け問題を解くことも可能

例; 最短経路を求めよ

問題

No.1473 おでぶなおばけさん解説

解答

def bfs(max_w):
    que = collections.deque([(0,0)]) # index, something val
    visited = [-1]*N
    while que:
        i, c = que.popleft() # queはFIFO
        if visited[i] >= 0:
            continue
        visited[i] = c
        for j, d in G[i]:
            if visited[j] == -1 and max_w <= d: # まだ未踏のノードであれば
                que.append((j,c+1)) # 自分の値に+1してqueに入れる
    return visited[-1]

例; 最短経路を求めよ(最短経路から解が導出できる)

問題

AtCoder Beginner Contest 088; D - Grid Repainting

解答

import collections
import math
H,W=map(int,input().split())
G=[list(input()) for h in range(H)]
que = collections.deque([(0,0)])
dp = [[-math.inf]*W for h in range(H)]
dp[0][0] = 0
def bfs():
    while que:
        cur = que.popleft()
        for a,b in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = cur[0] + a
            nw = cur[1] + b
            if nh > H-1 or nh < 0 or nw < 0 or nw > W-1:
                continue
            if G[nh][nw] == "#":
                continue
            if dp[nh][nw] != -math.inf:
                continue
            dp[nh][nw] = dp[cur[0]][cur[1]] + 1
            que.append( (nh, nw) )
bfs()

white_num = sum(sum([1 for e in line if e == "."]) for line in G)
if dp[H-1][W-1] != -math.inf:
    print(white_num - dp[H-1][W-1] - 1)
else:
    print(-1)

例; 0-1 bfsの適応例; 01で表現されるコストが存在する場合の最小コスト

問題

AtCoder Regular Contest 005; C - 器物損壊！高橋君

解説

とりあえずすべての探索をすることを目指すのだが、queの管理の方法が異なる
可能ならばコストがある所、つまり、壁は通りたくないのでqueの最後に追加するのに対して普通の道路はqueの最初に追加する
イメージとしては壁はFILOであり、道はFIFOである

解答

import collections
H, W = map(int, input().split())
G = []
for h in range(H):
    G.append(list(input()))

for h in range(H):
    for w in range(W):
        if G[h][w] == 's':
            sh, sw = h, w
        if G[h][w] == 'g':
            gh, gw = h, w

P = [[-1] * W for _ in range(H)]
P[sh][sw] = 0

que = collections.deque([(sh, sw)])
while que:
    h, w = que.popleft()
    for dh, dw in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        nh = dh + h
        nw = dw + w
        if not (0 <= nh < H and 0 <= nw < W and P[nh][nw] == -1):
            continue
        if G[nh][nw] == '#':
            P[nh][nw] = P[h][w] + 1
            que.append((nh, nw))
        elif G[nh][nw] in {".", "g"}:
            P[nh][nw] = P[h][w]
            que.appendleft((nh, nw))

print("YES" if P[gh][gw] <= 2 else "NO")

例; バケツで水を流し込んだとき水に接している面積を求める

問題

第１１回日本情報オリンピック予選

解説

イルミネーションを付ける場所 = 人目につく可能性のある場所 = 人目を水とみなす = 水を満たしたときの接する回数をカウントする
水で満たせるように探索範囲を少し拡張して拡張した場所から水を注ぐ

解答

import collections
import numpy as np
W,H=map(int,input().split())

G = np.zeros((H+2, W+2)).astype(int).tolist()
for h in range(1,H+1):
    for w, s in enumerate(map(int,input().split()), 1):
        G[h][w] = s
Vis = np.zeros((H+2, W+2)).astype(int).tolist()

def bfs(que):
    walls = 0
    while que:
        h, w, cnt = que.popleft()
        if Vis[h][w]:
            continue
        Vis[h][w] = 1
        if h % 2 == 0:
            action = ((-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1))
        else:
            action = ((-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1))
        for dh, dw in action:
            nh,nw=dh+h,dw+w
            if 0 <= nh < H+2 and 0 <= nw < W+2:
                # 0 -> 1
                if G[nh][nw] == 1:
                    walls += 1
                else:
                    que.append( (nh, nw, cnt) )
            else:
                continue
    return walls

que = collections.deque([(0,0,0)])
walls = bfs(que)
print(walls)

例; 木の直径を求める(典型)

問題

競プロ典型 90 問; 003 - Longest Circular Road

解説

木の直径は任意の点からの最長距離を計算する
再長距離のVから最長距離のV’を発見する
Vから見たV’が再長距離(かつ木の直径)

解答

submission

例; 辺の色の塗り分け問題

問題

AtCoder Beginner Contest 146; D - Coloring Edges on Tree

解説

色の塗り分けを行いたい場合、最大の色の個数は、最大の辺の数を持つ頂点の辺の数である
bfsで色を決めていき、すべての頂点の使用した色を管理しておき、それ以外の最小の色を次の辺に割り当てる
iteratorで回すことで、辺が多い頂点のループ数を減らせる

解答

import collections
import sys
input = sys.stdin.readline

N = int(input())

G = collections.defaultdict(collections.deque)
for n in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append( (b, n) )
    G[b].append( (a, n) )

K = max([len(v) for v in G.values()])


def bfs():
    que = collections.deque([0])
    bans = collections.defaultdict(set) # vの使用済みの色を保存する
    edge_color = [0]*(N-1) # eの可能性のある最小の色を保存する
    vtd = set()
    while que:
        i = que.popleft()
        if i in vtd:
            continue
        vtd.add(i)
        colors = iter(c for c in range(K) if c not in bans[i]) # iterにしないとめちゃ重い
        for j, edge in G[i]:
            if j in vtd:
                continue
            que.append(j)
            color = next(colors)
            edge_color[edge] = color + 1
            bans[i].add(color)
            bans[j].add(color)
    return edge_color

edge_color = bfs()
print(K)
print(*edge_color, sep="\n")