Atcoder水色への精選 100 問　幅優先探索(Python)

AtCoder Python 競プロ精進 精選100問

水色になるための精選100問、
今回は28~33までの「幅優先探索」です

qiita.com

前回↓
深さ優先探索
algo-archit.hatenablog.com

目次



28　ALDS_11_C - 幅優先探索

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

dequeと呼ばれる両端キューを用いることで問題を解くことができます
そのノードに訪問したか、そのノードまでの距離をそれぞれ格納するリストを用意しておき、
訪問済みでないノードにたどり着いた場合にキューを追加します

キューがすべてなくなった時の距離が答えです

pythonでの実装例

from collections import deque

inf = 10**10

n = int(input())
network = [[] for _ in range(n+1)]
length_list = [inf for _ in range(n+1)]
visited_list = [0 for _ in range(n+1)]

for _ in range(n):
    inputs = list(map(int,input().split()))
    u,k = inputs[:2]
    v = inputs[2:]
    network[u] += v

que = deque() # キューを作成

que.append(1)
length_list[1] = 0 

while que:
    node = que.popleft() # 先頭から要素を取得
    visited_list[node] = 1

    for i in network[node]:
        if visited_list[i]:
            continue
        
        que.append(i) # 
        visited_list[i] = 1
        
        # 長さ+1をしても現在より短くなる場合は更新
        if length_list[i] > length_list[node]+1:
            length_list[i] = length_list[node]+1

for i in range(1,n+1):
    if length_list[i] == inf:
        print(i,-1)
    else:
        print(i,length_list[i])



29　AtCoder Beginner Contest 007 C - 幅優先探索

問題文
atcoder.jp

マス目状の問題の場合でも二次元型のリストを使って同じように解くことができます
壁に当たらず、かつ訪問済みでないマスをキューに追加して答えのマスまでの距離を求めます

pythonでの実装例

from collections import deque

inf = 10**10

R,C = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())

c = [input() for _ in range(R)]

sy -= 1
sx -= 1
gy -= 1
gx -= 1

inf = 10**10
visited = [[0 for i in range(C)] for j in range(R)]
length = [[inf for i in range(C)] for j in range(R)]

que = deque([]) 

que.append([sy,sx])
visited[sy][sx] = 1
length[sy][sx] = 0

while que:
    y,x = que.popleft()

    for y_move,x_move in [[-1,0],[1,0],[0,-1],[0,1]]:
        ny = y+y_move
        nx = x+x_move

        if visited[ny][nx] or c[ny][nx] == "#":
            continue

        que.append([ny,nx])
        visited[ny][nx] = 1

        if length[ny][nx] > length[y][x]+1:
            length[ny][nx] = length[y][x]+1

print(length[gy][gx])



30　JOI 2011 予選 5 - チーズ

問題文
atcoder.jp

硬さ１のチーズから順番に食べていけばOKです
順番を辞書に格納しておき、各中継地点までのかかる時間（距離）を合計したものが答えとなります

pythonでの実装例

from collections import deque,defaultdict

inf = 10**10

h,w,n = map(int,input().split())
town = [input() for _ in range(h)]
factory = defaultdict(int)

# スタートと工場の順番を辞書に入れる(スタートを0とする)
for i in range(h):
    for j in range(w):
        if town[i][j] == "S":
            factory[0] = [i,j]
        elif town[i][j] == "X" or town[i][j] == ".":
            continue
        else:
            factory[int(town[i][j])] = [i,j]

def bfs(sy,sx,gy,gx):
    visited = [[0 for j in range(w)]for i in range(h)]
    length = [[inf for j in range(w)]for i in range(h)]

    que = deque([])
    que.append([sy,sx])
    visited[sy][sx] = 1
    length[sy][sx] = 0
    
    while que:
        y,x = que.popleft()

        for i,j in [[-1,0],[0,1],[0,-1],[1,0]]:
            ny,nx = y+i,x+j

            if 0 <= ny < h and 0 <= nx < w and visited[ny][nx]== 0 and town[ny][nx] != "X":
                que.append([ny,nx])
                visited[ny][nx] = 1
                length[ny][nx] = length[y][x]+1

    return length[gy][gx]

total = 0 # 最終的にかかる時間

# 順番に経路をたどっていく
for i in range(1,n+1):
    sy,sx = factory[i-1]
    gy,gx = factory[i]

    total += bfs(sy,sx,gy,gx)

print(total)



31　JOI 2012 予選 5 - イルミネーション

問題文
atcoder.jp

やっかいな問題に見えますが、移動できる方向が４→６に増えたと考えれば大丈夫です（偶奇の時の場合分けに注意）
今回はマス目の外側に１つ分余分なマスを作り、自由に動き回ったときに、何回壁に当たったかをカウントします

このときのカウント数がイルミネーションする壁面の個数になります

この問題に関しては公式の解説図がとっっっても分かりやすかったので確認してみてください↓
www.ioi-jp.org

pythonでの実装例

from collections import deque

inf = 10**10

w,h = map(int,input().split())
field = [[0 for j in range(w+2)]for i in range(h+2)]
visited = [[0 for j in range(w+2)]for i in range(h+2)]

for i in range(h):
    field[i+1][1:w+1] = map(int,input().split())

# どの行かで動き方が異なる
odd_move = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[0,-1]]
even_move = [[-1,-1],[-1,0],[0,1],[1,0],[1,-1],[0,-1]]

que = deque([])
que.append([0,0])
visited[0][0] = 1

# 壁にぶつかった回数をカウント
collision = 0

while que:
    y,x = que.popleft()

    if y%2 == 1:
        move = odd_move
    else:
        move = even_move

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h+2 or nx < 0 or nx >= w+2:
            continue
        elif field[ny][nx] == 1:
            collision += 1 # 壁にぶつかったのでカウント
            continue
        elif visited[ny][nx]:
            continue
        else:
            que.append([ny,nx])
            visited[ny][nx] = 1

print(collision)



32　AOJ 1166 - 迷図と命ず

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166

一見ややこしくてわかりにくい問題ですが、マス目を新しく自分で作り、
縦横の４方向に動くことができるかを壁のリストから参照します

端側の処理だけ注意していれば問題なく解くことができます

pythonでの実装例

from collections import deque

inf = 10**10

# 0,0入力が来るまで
while True:
    w,h = map(int,input().split())

    if w == 0 and h == 0:
        break
    
    v_wall = [] # 垂直壁
    h_wall = [] # 水平壁

    for i in range(2*h-1):
        if i%2 == 0:
            v_wall.append(list(map(int,input().split())))
        else:
            h_wall.append(list(map(int,input().split())))

    visited = [[0 for i in range(w)] for j in range(h)]
    length = [[inf for i in range(w)] for j in range(h)]

    visited[0][0] = 1
    length[0][0] = 1

    que = deque([])

    que.append([0,0])

    while que:
        y,x = que.popleft()
        can_go = [] # 行くことができる方向
      
        # 左確認
        if x != 0 and v_wall[y][x-1] != 1:
            can_go.append([y,x-1])
        # 右確認
        if x != w-1 and v_wall[y][x] != 1:
            can_go.append([y,x+1])
        # 上確認
        if y != 0 and h_wall[y-1][x] != 1:
            can_go.append([y-1,x])
        # 下確認
        if y != h-1 and h_wall[y][x] != 1:
            can_go.append([y+1,x])
        
        if not can_go:
            continue

        for ny,nx in can_go:
            if visited[ny][nx]:
                continue

            que.append([ny,nx])
            visited[ny][nx] = 1
            length[ny][nx] = length[y][x]+1
    
    if length[h-1][w-1] != inf:
        print(length[h-1][w-1])
    else:
        print(0)



33　AtCoder Beginner Contest 088 D - Grid Repainting

問題文
atcoder.jp

問題文を言い換えると
「最短距離のマス目以外を黒くするにはあと何マス塗りつぶせばいいですか？」
となります

よって答えは、
「全マスの個数H＊W - 最短距離 - すでに黒いマスの個数」
です

pythonでの実装例

from collections import deque

inf = 10**10

h,w = map(int,input().split())
field = [input() for _ in range(h)]

length = [[inf for j in range(w)]for i in range(h)]
visited = [[0 for j in range(w)]for i in range(h)]

move = [[-1,0],[1,0],[0,-1],[0,1]]

que = deque([])
que.append([0,0])
length[0][0] = 1 # １スタート
visited[0][0] = 1

white = 0

for i in range(h):
    white += field[i].count(".")

while que:
    y,x = que.popleft()

    for i,j in move:
        ny,nx = y+i,x+j

        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        elif field[ny][nx] == "#":
            continue
        elif visited[ny][nx] == 1:
            continue
        
        visited[ny][nx] = 1
        que.append([ny,nx])
        length[ny][nx] = length[y][x] + 1

if length[h-1][w-1] == inf:
    print(-1)
else:
    print(white-length[h-1][w-1]) # 白の総数から最小距離分引く