Pythonで解く【初中級者が解くべき過去問精選 100 問】(028 - 033 幅優先探索)

# 1. 目的
[初中級者が解くべき過去問精選 100 問](https://qiita.com/e869120/items/eb50fdaece12be418faa)をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「028 - 033 幅優先探索」です。

# 2. 総括
 ```DFS``` ができれば```BFS```はほぼ同じです。
違いは```deque()```からポップする箇所で```DFS```では```pop()```を、```BFS```では```popleft()```を使います。


# 3. 本編
## 028 - 033 幅優先探索

### 028. [ALDS_11_C - 幅優先探索](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/a5951557-9392-2fe3-76bf-a978aba6375b.png)

#### 回答
```python

from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n):
    i, num, *nodes = map(int, input().split()) # *で余分を回収
    graph[i] = nodes # 有向グラフ
visited = [-1] * (n+1)

q = deque()
q.append(1)
visited[1] = 0

while q:
    node = q.popleft()

    for next in graph[node]:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = visited[node] + 1
        
for i, num in enumerate(visited[1:]):
    print(i+1, num)

```

これは基礎問題。
ここで自分の型を作っておけば、あとは少しいじるだけで他の問題を解くことができると思われます。


 ```BFS``` の流れをざっくり示すと、
1. ```visited``` で探索先の記録ようのリストをつくる
2. ```deque()``` をとりあえず準備して、初期値をいれる
3. ```deque()``` が空になるまで```while```を回す
4. ```popleft()```で先入れ先出しで値を取り出す
5. 取り出した値から```graph```を調べて行先を調べる
6. 行先が探索済みか否かを判定
7. 探索してない場合は```append``` して```visited``` を更新

です。


---

### 029. [AtCoder Beginner Contest 007 C - 幅優先探索](https://atcoder.jp/contests/abc007/tasks/abc007_3)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/0fdd68d4-85e7-343f-4b11-3c8d0cdf9e15.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/d5946c11-dc0f-d650-9f28-a902a3c25163.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/d726d3bb-1062-96d3-dd71-90951ef4aba7.png)

#### 回答
```python

from collections import deque

R, C = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1 # 0インデックスに修正
sx -= 1
gy, gx = map(int, input().split())
gy -= 1 # 0インデックスに修正
gx -= 1
grid = [list(input()) for _ in range(R)]
visited = [[-1] * C for _ in range(R)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

q = deque()
q.append((sy, sx))
visited[sy][sx] = 0

while q:
    start_y, start_x = q.popleft()

    for dy, dx in moves:
        moved_y = start_y + dy
        moved_x = start_x + dx

        if grid[moved_y][moved_x] == '#':
            continue
        if visited[moved_y][moved_x] != -1:
            continue
        visited[moved_y][moved_x] = visited[start_y][start_x] + 1
        q.append((moved_y, moved_x))

print(visited[gy][gx])

```

これは典型中の典型です。
とりあえず覚える、です。


---

### 030. [JOI 2011 予選 5 - チーズ](https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_e)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e54e3abe-e719-f8f8-a0d8-c80b7ec843b7.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/8a6b13b4-ff4c-5029-1f30-874c9a29be08.png)

#### 回答
```python
from collections import deque

def bfs(start_y, start_x, target_cheese, H, W, grid):

    visited = [[-1] * W for _ in range(H)]
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    q = deque()
    q.append((start_y, start_x))
    visited[start_y][start_x] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx

            if moved_y < 0 or H - 1 < moved_y or moved_x < 0 or W -1 < moved_x:
                continue
            if grid[moved_y][moved_x] == 'X':
                continue
            if visited[moved_y][moved_x] != -1:
                continue
            if grid[moved_y][moved_x] == target_cheese:
                visited[moved_y][moved_x] = visited[y][x] + 1
                return visited[moved_y][moved_x]
 
            visited[moved_y][moved_x] = visited[y][x] + 1
            q.append((moved_y, moved_x))
            

if __name__ == "__main__":
    H, W, N = map(int, input().split())
    grid = [list(input()) for _ in range(H)] # Sは巣でスタート、数字はチーズの硬さ、Xは障害物、.は空き地
    # ネズミは数字の順番にチーズを食べる
    # 各数字から次の数字へのBFSを考える
    # スタートと各数字の位置を先に把握する
    start_y, start_x = 0, 0
    cheese = [(0, 0) for _ in range(10)] # 初期値を(0, 0)にしておく
    count = 0 # countにチーズの数をいれておく
    for row in range(H):
        for col in range(W):
            if grid[row][col] == '.' or grid[row][col] == 'X':
                continue
            elif grid[row][col] == 'S':
                start_y, start_x = row, col
            else:
                grid[row][col] = int(grid[row][col]) # グリッドの中身を数字に変えておく
                cheese[int(grid[row][col])] = (row, col)
                count += 1
                
    # ------- [すべての点を探索] ----------
    target_cheese = 1
    time_count = 0
    while target_cheese <= count:
        time_count += bfs(start_y, start_x, target_cheese, H, W, grid)
        start_y, start_x = cheese[target_cheese]
        target_cheese += 1

    print(time_count)

```

やや実装が重いです。
問題文より、ネズミは数字の小さいチーズから大きいチーズへと順番に食べていきますので、各数字から次の数字への```BFS```を行ってやればよさそうです。
なので、スタート位置とゴール位置が決まっている```BFS```を、チーズの数字の順番に設定してやり、
```S```→```1```の```BFS```、```1```→```2```の```BFS```、```2```→```3```の```BFS``` ・・・と行っていき、合計の最短距離が答えとなります。

---

### 031. [JOI 2012 予選 5 - イルミネーション](https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_e)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/79b57529-784e-dfc2-e3d2-23689cda724a.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/1d705f78-419e-4c9f-3e95-7c217575a354.png)

#### 回答
```python

# girdの上下左右に0ますを全て付け加えて、
# 座標(0,0)から行ける各0点が接する1の数を足しあげる

from collections import deque

# ---------- [建物がない場所が隣接している建物の数を数える] --------------
def check_walls(y, x, grid, W, H, even_moves, add_moves):
    count = 0

    if y % 2 == 0:
        moves = even_moves
    else:
        moves = add_moves
    
    for dy, dx in moves:
        moved_y = y + dy
        moved_x = x + dx
        if moved_y < 0 or H + 1 < moved_y or moved_x < 0 or W + 1 < moved_x:
            continue
        if grid[moved_y][moved_x] == 1:
            count += 1
    
    return count

if __name__ == "__main__":
    # ---------- [入力受取] --------------
    W, H = map(int, input().split())
    grid = []
    grid.append([0] * (W+2))
    for _ in range(H):
        temp = list(map(int, input().split()))
        temp = [0] + temp + [0]
        grid.append(temp)
    grid.append([0] * (W+2))
    visited = [[-1] * (W+2) for _ in range(H+2)]
    answer_count = 0
    # ---------- [偶数と奇数で動ける方向が異なる] --------------
    even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] # 左上から時計回り
    add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] # 左上から時計回り
    # ---------- [初期値設定] --------------
    q = deque()
    q.append((0, 0)) # (0, 0)から行ける建物がない場所についてBFSを実施する
    count = check_walls(0, 0, grid, W, H, even_moves, add_moves) # 隣接する建物数をカウント
    visited[0][0] = count
    answer_count += count
    # ---------- [BFS開始] --------------
    while q:
        y, x = q.popleft()

        if y % 2 == 0:
            moves = even_moves
        else:
            moves = add_moves
        
        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx
            if moved_y < 0 or H + 1 < moved_y or moved_x < 0 or W + 1 < moved_x:
                continue
            if grid[moved_y][moved_x] == 1:
                continue
            if visited[moved_y][moved_x] != -1:
                continue
            q.append((moved_y, moved_x))
            count = check_walls(moved_y, moved_x, grid, W, H, even_moves, add_moves)
            visited[moved_y][moved_x] = count
            answer_count += count

    print(answer_count)

```

多くの問題は碁盤目状をベースとしたものですが、本問題は1つのマスが6角形であり若干異なります。
しかし、考え方も解き方も大きくは変わらず、変更するところは、```BFS```の移動の座標の設定方法です。
具体的には、僕の場合```moves```で定義している部分です。

本問題では```y```座標が偶数と奇数の場合で、各マスから動ける先が異なってきます。
したがってそれぞれ下記のように定義をしてやります

```python

even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] # 左上から時計回り
add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] # 左上から時計回り

```

通常の碁盤目状であれば上下左右、または、上下左右+斜めの移動成分を下記のように定義しますので、ここだけが違います。


```python

moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 上下左右のみの場合

moves = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)] # 上下左右+斜めの場合

```

ここさえ押さえればあとは下記方針として解いていきます
1. 大きな方針は、「建物がない箇所」を```BFS```で探索し、各箇所で隣接する建物を数えてその合計が答え
2. そのために、まずはデフォルトで受け取るgridの上下左右に追加で「建物がない箇所」を追加する
3. gridの左上(0, 0)から```BFS```を実施
4. その際に```visited```に記録するのは通常の0, 1ではなく、隣接する建物の数
5. そのため隣接する建物の数を数えるための関数である```check_walls```を作成しておく
6. ```BFS```を行うにあたっては```y```が偶数の場合と奇数の場合で動き方違うので注意する
7. ```BFS```を一通りおこなって、```check_walls```で返ってきた数を合計したものが答え

です。


---

### 032. [AOJ 1166 - 迷図と命ず](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/dfecb51d-6dbe-9b0d-48c2-20c70fda844d.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e4164b35-1005-6002-04e5-4bb1622de76e.png)

#### 回答
```python

from collections import deque

def main(w, h):
    tatebou = []
    yokobou = [[0] * w]
    for _ in range(h-1):
        tate = [0] + list(map(int, input().split()))
        yoko = list(map(int, input().split()))
        tatebou.append(tate)
        yokobou.append(yoko)
    tate = [0] + list(map(int, input().split()))
    tatebou.append(tate)
    visited = [[0] * w for _ in range(h)]
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

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

        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx

            if dy == 1 and dx == 0:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if yokobou[moved_y][moved_x] == 1: # 下に行くときは動く先が1のときだめ
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))

            elif dy == -1 and dx == 0:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if yokobou[y][moved_x] == 1: # 上に行くときは自分が1のときだめ
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))

            elif dy == 0 and dx == 1:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if tatebou[moved_y][moved_x] == 1: # 右に行くときは動く先が1のときだめ
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))
            else: # dy == 0 and dx == -1
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if tatebou[moved_y][x] == 1: # 左に行くときは自分が1のときだめ
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))
            
    return visited[h-1][w-1]


if __name__ == "__main__":

    answer_list = []
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        answer = main(w, h)
        answer_list.append(answer)

    for answer in answer_list:
        print(answer)


```

基本的に問題29とやることは同じです。
異なる点は、当たり判定です。問題29は「マスそれ自体に行けない」という当たり判定でしたので簡単ですが、この問題は、「マス」ではなく「壁」です。
なので、通常の```BFS```では必要ない場合分けを行う必要があります。
具体的には、上下左右の動き方それぞれで、下記のように当たり判定を変える必要があります。


```python


            if dy == 1 and dx == 0:
                if yokobou[moved_y][moved_x] == 1: # 下に行くときは動く先が1のときだめ
                    continue
            elif dy == -1 and dx == 0:
                if yokobou[y][moved_x] == 1: # 上に行くときは自分が1のときだめ
                    continue
            elif dy == 0 and dx == 1:
                if tatebou[moved_y][moved_x] == 1: # 右に行くときは動く先が1のときだめ
                    continue
            else: # dy == 0 and dx == -1
                if tatebou[moved_y][x] == 1: # 左に行くときは自分が1のときだめ
                    continue

```

この当たり判定以外は普通に書くだけです。


---

### 033. [AtCoder Beginner Contest 088 D - Grid Repainting](https://atcoder.jp/contests/abc088/tasks/abc088_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/48dcace0-132c-1d62-458b-f461c4949787.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/2b40913c-ffca-5e1a-18f5-1acf782bc7b4.png)


#### 回答
```python

# 白だけ動いて(0,0)から(H-1, W-1)に行く
# その際にできるだけ黒を増やす
# 全体の白から最短距離を除いたものが答え

from collections import deque


H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)] # .は白、#は黒
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

q = deque()
q.append((0, 0))
visited[0][0] = 0

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

    for dy, dx in moves:
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H-1 < moved_y or moved_x < 0 or W-1 < moved_x:
            continue
        if grid[moved_y][moved_x] == '#':
            continue
        if visited[moved_y][moved_x] != -1:
            continue

        visited[moved_y][moved_x] = visited[y][x] + 1
        q.append((moved_y, moved_x))

min_route = visited[H-1][W-1]

if min_route == -1:
    answer = -1
else:
    total_white = 0
    for row in grid:
        total_white += row.count('.')

    answer = total_white - min_route - 1

print(answer)


```

ほかの問題を解けたのであれば、これは結構簡単です。
問題をかみ砕いて解釈すると「できるだけ黒に塗って左上から右下に移動するときの黒に塗った数」が回答になります。
これをもう少し解きやすいように解釈すると「左上から右下に最短距離で移動したときに、その他通っていないところの数」となります。
これがわかれば、普通に```BFS```で最短距離を算定して、全体のから引けばよいとわかります。

なので、方針は
1. ```(0,0)```スタート、```(H-1, W-1)```ゴールで最短距離```min_route```を算出
2. 全体の白の数```total_white ```を算出
3. ```total_white ```から```min_route```を引いたものが答え（```min_route```はゼロスタートなので-1を追加でする）

です。




---