初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #6 ( 深さ優先探索（DFS）編 )
新年あけましておめでとうございます！！（おそっ）
今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！
精選100問って何？
記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。
記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。
今回は第６回目の深さ優先探索！！
過去の記事についてはこちら！！
全探索シリーズ
第１回：全列挙
第２回：工夫して通り数を減らす全列挙
第３回：ビット全探索
第４回：順列全探索
第５回：二分探索
深さ優先探索
深さ優先探索の分野は全部で４問あるので、紹介したいと思います！
24. Depth First Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja
個人的にはいきなり難しすぎて１ヶ月ほど放置してました...
これはまず３種類のグループ分けをして調べていきます。
- 1. まだ訪問してない頂点（下記コードのvisitでbool判定）
- 2. 訪問した頂点 かつ 行きしか調べてない（下記コードのgoが行きの判定）
- 3. 訪問した頂点 かつ 行きも帰りも調べてある（下記コードのbackが帰りの判定）
この上記のものを上の方から優先度が高くなるように調べていくと見つけることができます。
慣れるまではもう少し時間がかかりそうです。
n = int(input()) graph = [[0] * n 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][a[j + 2] - 1] = 1 visit = [False] * n # 訪問済みかどうかの判定 go = [0] * n # 発見時刻 back = [0] * n # 完了時刻 time = 0 # その時の時刻 def dfs(i): global time time += 1 go[i] = time visit[i] = True for j in range(n): if visit[j] == False and graph[i][j] == 1: # 未訪問かつ行ける所 dfs(j) time += 1 back[i] = time for i in range(n): if not visit[i]: dfs(i) for i in range(n): print(i + 1, go[i], back[i])
25. How Many Islands?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp
これはdequeを使う問題です。
最初は全くわからず10人くらいのACしている方のコードを写経していると少しずつ理解してきて書けるようになりました。
コードの流れとしてはまず一つ一つのマスを見ていき、そこが陸であった場合dfsで行ける場所全てを訪問済みにして ans += 1 として全部のマスを調べていくイメージで解きました。
from collections import deque def dfs(y, x): d = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]] # 8方向に対する変化量 q = deque() q.append([y, x]) while q: dy, dx = q.popleft() c[dy][dx] = 0 for i, j in d: if 0 <= dy + i <= h - 1 and 0 <= dx + j <= w - 1: # これよく忘れがちでREになる if c[dy + i][dx + j] == 1: c[dy + i][dx + j] = 0 q.append([dy + i, dx + j]) while True: w, h = map(int,input().split()) if (w, h) == (0, 0): exit() c = [list(map(int,input().split())) for _ in range(h)] ans = 0 for i in range(h): for j in range(w): if c[i][j] == 1: ans += 1 dfs(i, j) print(ans)
26. D - Ki
https://atcoder.jp/contests/abc138/tasks/abc138_d
こちらもqueueを使う問題です。
やっぱりこの分野はまだまだ難しく感じます。
方針としてはチェック済みでないノードに隣接してるものの合計を足していく方針でACできます。隣接行列はDFSでは本当によく使うので必ず取得が必要となってきます。
from collections import deque n, q = map(int,input().split()) graph = [[] for _ in range(n)] # 隣接行列の作成 for i in range(n - 1): a, b = map(int,input().split()) graph[a - 1].append(b - 1) graph[b - 1].append(a - 1) ans = [0] * n # 答えとなるカウンターの値 for i in range(q): p, x = map(int,input().split()) ans[p - 1] += x q = deque() q.append(0) check = [0] * n while q: v = q.popleft() check[v] = 1 # queueに入ってるノードをチェック済みにする for i in graph[v]: if check[i] != 0: continue # 未チェックの状態なら調べ上げる ans[i] += ans[v] q.append(i) print(*ans)
27. D - 薄氷渡り
https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d
この問題も非常に苦戦しました。
2時間くらいかけた上にTLの方人も聞いた。
方針としては全てのマスについて調べていって、そのマスが薄氷だった場合DFSを開始して最後に最大値を適宜最大値を更新するイメージです。
個人的に難しく感じた点は19行目の
check[y][x] = False
にする所です。これはDFSの探索が奥まで終わったらもう一度元のマスを
初期化するというものでなかなか理解するのに苦労しました。
n = int(input()) m = int(input()) grid = [[0] * (n) for _ in range(m)] # 入力した値を打ち込む場所 d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 変化量[y, x] for i in range(m): l = list(map(int,input().split())) for j in range(n): grid[i][j] = l[j] def dfs(y, x, num): cnt = num check[y][x] = True for i, j in d: if not (0 <= y + i <= m - 1 and 0 <= x + j <= n - 1): continue # 範囲外なら調べない if check[y + i][x + j] == True: continue # 既にチェック済みの場所なら調べない if grid[y + i][x + j] == 0: continue # 薄氷でなければ調べない cnt = max(cnt, dfs(y + i, x + j, num + 1)) check[y][x] = False return cnt ans = 0 # 答え for i in range(m): for j in range(n): if grid[i][j] == 1: check = [[False] * n for _ in range(m)] ans = max(ans, dfs(i, j, 1)) print(ans)
最後に
最後に記事を投稿してからかなりの日付が開いてしまいました。
DFSは１度も書いたことがなく全て０から調べていたので時間がかかりました。
次回はBFSですが、こちらも早く投稿はしたいですが、おそらく時間はかかります。
でも頑張って解くので応援よろしくお願いします！
最後まで見てくださった方、本当にありがとうございました！
コードの指摘事項・アドバイス等ありましたら、コメントにてお知らせください。
