【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】

**目指せ水色コーダー！！！！！！**

ということで、 
[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](
https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)(@e869120さん)
>
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

こちらの記事の`初中級者が解くべき過去問精選 100 問`
を**Python**で解いていきます！
@e869120さんに感謝！！！！！！

###過去記事リンク
**全探索：全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】](https://qiita.com/rudorufu1981/items/8ae8beeba7b047f2687c)
**全探索：工夫して通り数を減らす全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】](https://qiita.com/rudorufu1981/items/282e06a6898f021b5e7f)
**全探索：ビット全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
**全探索：順列全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】](https://qiita.com/rudorufu1981/items/71abd5320a636e9146cb)
**二分探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】](https://qiita.com/rudorufu1981/items/2683c3988b246c9cf9ce)
**深さ優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】](https://qiita.com/rudorufu1981/items/e39aa16d73615c7e589f)
**幅優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】](https://qiita.com/rudorufu1981/items/4804987152ad22f3fcb4)

#「Part6」〜深さ優先探索(DFS)編〜
以下の4問を解いていきます！

>
#####深さ優先探索
24　ALDS_11_B - 深さ優先探索　基本問題です。
25　AOJ 1160 - 島はいくつある？　グラフの連結成分数は、深さ優先探索で計算できます。
26　AtCoder Beginner Contest 138 D - Ki　木構造の問題の多くは、深さ優先探索を使います。
27　JOI 2009 予選 4 - 薄氷渡り　深さ優先探索は、木構造だけではありません、ということを教えてくれる問題です。再帰関数を使って解けます。


#DFSの前提知識
・以下の3点を前提として、記事を書いていきます！
**①スタックとキューについて**
まずはけんちょんさんの記事
[スタックとキューを極める！ 〜 考え方と使い所を特集 〜](https://qiita.com/drken/items/6a95b57d2e374a3d3292)
を読んで、スタックとキューについて**雰囲気理解する！**

**②DFSとグラフについて**
またまたけんちょんさんの記事
[DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】](https://qiita.com/drken/items/4a7869c5e304883f539b)
[DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】](https://qiita.com/drken/items/a803d4fc4a727e02f7ba)
を読んで、DFSとグラフについて**雰囲気理解する！**

**③あとは、PythonでのDFSの具体的な実装方法**
として、
以下のサイトがわかりやすかったので、この2つのサイト
**◆ふつうのグラフまたは木の場合**
[Pythonでアルゴリズム（深さ優先探索、dfs）](https://qiita.com/takayg1/items/7008e4c9584e42ae13c7)
**◆グリッドグラフの場合**
[Pythonで深さ優先探索(DFS)を実装してみる-ATC001](https://nashidos.hatenablog.com/entry/2020/01/04/234842)
を**じっくり**読んでDFSとグラフについて**深く理解する！**

①②③の前提があれば、あとは実際に手を動かせば身につきます！！！

※補足1
DFSは**再帰Ver**と**スタックVer**の2つの実装方法がありますが、
**この記事ではスタックVerの実装に統一します！！！**
(BFSに応用が効きやすい？+速度も早い？+スタックオーバーフローを起こさない？ため)

※補足2
今回(**Part6**)の記事から、入力を
`input()`→`sys.stdin.readline().rstrip()`
に変えています！
[【Python】競プロテンプレ【AtCoder】](https://qiita.com/rudorufu1981/items/c6bc5e4d72cfe1cb7f14)
テンプレ用の記事も作ったので、よかったら使ってください〜

#[24　ALDS_11_B - 深さ優先探索](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B)
典型的なグラフ問題！

**`graph = {i:collections.deque() for i in range(1,N+1)}`**
または、
**`graph = {i:[] for i in range(1,N+1)}`**
**これがグラフのテンプレ！**

DFSの実装初めてだったけど、
上のサイトの通り実装してみると**なんとか実装できた！**
コードは長いけど、**難易度はたいしたことない！！！**

ポイントは、この2行！！！

```
seen[j] = 1
stack.append(j)
```
```
seen[g_NO] = 1
stack.append(g_NO)
```

〜覚え方〜
①**家政婦は見た！**（ドラマ）ので、
`seen`を`0(False)`→`1(True)`にする！
②家政婦は見たら、ストックに入れます！！！
**（家政婦がゴミを見たので、ゴミ箱に入れるイメージ！！！）**

このイメージが頭にあれば、実装の時に脳死でコードが書ける！


```python:test.py
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
    u,k,*v = x
    for y in v:
        graph[u].append(y)
seen = [0]*(n+1) #1_indexed
stack = []
time = 0
seentime = [0]*(n+1) #1_indexed
donetime = [0]*(n+1) #1_indexed
def dfs(j):
    global time
    seen[j] = 1
    stack.append(j)
    time += 1
    seentime[j] = time
    while stack:
        s = stack[-1]
        if not graph[s]:
            stack.pop()
            time += 1
            donetime[s] = time
            continue
        g_NO = graph[s].popleft()
        if seen[g_NO]:
            continue
        seen[g_NO] = 1
        stack.append(g_NO)
        time += 1
        seentime[g_NO] = time
for j in range(1,n+1):
    if seen[j]:
        continue
    dfs(j)
for k,a,b in zip(range(1,n+1),seentime[1:],donetime[1:]):
    print(k,a,b)
```

`def dfs()`なんて書く必要ないけど、DFSの記述とわかりやすいように`def`にしてみた！

また、グラフ問題は
「0」からではなく「1」から始まることがほとんどだと思うので
`1_indexed`でコード全体を統一！

`global`も初めて使ってみたけどなるほど！って感じ！

あとコードを書いていて意識したことは、
**`continue`をできるだけ使って、条件以下のコードを走らせないようにして可読性をあげました！**
DFSは特にネストが深くなりがち！（＝複雑になりがち＝バグがうまれやすくなる！）
※過去記事参照
[【リーダブルコード】内容を5つ抜粋！【競技プログラミング】](https://qiita.com/rudorufu1981/items/81f305b4686ab8cc5120)

**家政婦は見た！（2回目）**

#[25　AOJ 1160 - 島はいくつある？](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp)
典型的なグリッドグラフ問題！
ふつうのグラフの問題と考え方は同じ！
上のサイトを参考にしたが、**案外スラスラかけた！**
**家政婦は見た！（3回目）**


```python:test.py
import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
    w,h = LI()
    if w==h==0:
        break
    ans = 0
    c = [LI() for _ in range(h)]
    seen = [[0]*w for _ in range(h)]
    stack = []
    dhdw = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
    def dfs(H,W):
        seen[H][W] = 1
        stack.append([H,W])
        while stack:
            sh,sw = stack.pop()
            for dh,dw in dhdw:
                nh,nw = sh+dh,sw+dw
                if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw] or c[nh][nw]==0:
                    continue
                seen[nh][nw] = 1
                stack.append([nh,nw])
    for H,W in itertools.product(range(h),range(w)):
        if seen[H][W] or c[H][W]==0:
            continue
        ans += 1
        dfs(H,W)
    print(ans)
```

#[26　AtCoder Beginner Contest 138 D - Ki](https://atcoder.jp/contests/abc138/tasks/abc138_d)
Difficulty:923
**初見で解けませんでした！！！**
計算量でつまずき、根の考え方でもつまずいた！
だけど、次からは似た問題きても解ける**「木」**がする！！！

ポイントはこの2点！

- 木は無向グラフとして考える
- 問題文よりこの木全体の根は頂点1

根より下にある頂点は全て、基準の根のポイントが追加されていく感じ〜
ACにならなかった人はこちらの記事も参考に！！！
[AtCoder Beginner Contest 138 D - Ki のテストケースがコンテスト後に増えている件について (修正版)](https://qiita.com/c-yan/items/887e2c2f410ecec60650)

**家政婦は見た！（4回目）**

```python:test.py
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_indexed
graph = {i:collections.deque() for i in range(1,N+1)} #1_indexed
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_indexed
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
```
ちなみに、
冒頭の補足2で記載した
>
今回(**Part6**)の記事から、入力を
`input()`→`sys.stdin.readline().rstrip()`
に変えています！


これの原因はこの問題ですw

TLEで苦戦していてところ、できる人のコード見てたら、
`sys.stdin.readline()`
使ってるなぁ・・・
一応使ってみるかと使ったところ、まさかのACになってびっくり！
調べてみると、**`input()`が激遅であることが判明！！！**
参考記事
[Pythonの知っておくと良い細かい処理速度の違い8個](https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline)

ほかにも計算量について、コードの改善余地はあるが、
(`ab`や`px`の受け取りのところとか)
ACになったからまあいいや〜

#[27　JOI 2009 予選 4 - 薄氷渡り](https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d)
**こちらも初見で解けませんでした！！！**

まさかの**家政婦は見た！(seen)**が使えない問題！！！
過去記事
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】](https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
の部分和問題もDFSで解ける問題なのですが、
**家政婦は見た！(seen)**が使えない場合は、**家政婦は見た！(seen)**に変わるものを自分で考えないといけないので難易度高め！

- Part3の部分和問題：**indexとsum**
- 今回の問題：**スタック時の位置、過去の履歴**

**難しい問題をたくさん解いて慣れていくしかなさそう！**

```python:test.py
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
m = I()
n = I()
area = [LI() for _ in range(n)]
ans = 0
dndm = [[1,0],[-1,0],[0,1],[0,-1]]
stack = [] #スタック時の位置、過去の履歴
def dfs(i,j):
    global ans
    stack.append([[i,j],set()])
    while stack:
        [sn,sm],history = stack.pop()
        ans = max(ans,len(history))
        for dn,dm in dndm:
            nn,nm = sn+dn,sm+dm
            if not(0<=nn<=n-1) or not(0<=nm<=m-1) or area[nn][nm]==0 or ((nn,nm) in history):
                continue
            stack.append([[nn,nm],history | {(nn,nm)}])
for i,j in itertools.product(range(n),range(m)):
    if area[i][j]==1:
        dfs(i,j)
print(ans)
```

※補足

```
history | {(nn,nm)}
```
の
`|`は`和集合`です！(ビット演算子のORでもある)
また、
`&`が`積集合`です！(ビット演算子のANDでもある)
`^`が`どちらか一方の集合`です！(ビット演算子のXORでもある)
※過去記事参照
[【Python】ARC006A(集合(set)最強説)【AtCoder】](https://qiita.com/rudorufu1981/items/6676031eac883b3a9947)

次回は、以下の6問を解いていきます！

>
#####幅優先探索
28　ALDS_11_C - 幅優先探索　基本問題です。
29　AtCoder Beginner Contest 007 C - 幅優先探索　重み無しグラフの最短経路問題は、幅優先探索で解けます。
30　JOI 2011 予選 5 - チーズ
31　JOI 2012 予選 5 - イルミネーション　少し実装が重いですが、頑張れば解けます。
32　AOJ 1166 - 迷図と命ず　実装が少し重いです。
33　AtCoder Beginner Contest 088 D - Grid Repainting　これが解ければ、幅優先探索に慣れたと思って良いです。

Part6/22
おわり！

[次(Part7/22)へ](https://qiita.com/rudorufu1981/items/4804987152ad22f3fcb4)