深さ優先探索

はじめに 今回は深さ優先探索の4問をやりました！ 精選100問はこちら！ 24 ALDS_11_B - 深さ優先探索 問題はこちらです！ 問題文↓ グラフを与えるので、小さい順にDFSしてください 基本問題でした！ コードは以下のようになりました #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i…

atcoder.jp・説明 DFSで解ける。Aiから行けるBiをDFSしていき、原点からの距離を(distx, disty)で管理する。 注意点として、入力で g[b].append((a,-1*c,-1*d)) bから見たaの座標もappendしないといけないことに注意。 import sys sys.setrecursionlimit(10**6) n,m=map(int,input().split()) g=[[] for _ in range(n)] for _ in range(m): a,b,c,d=map(int,input().split()) a-=1 b-=1 g[a].a…

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 引数に頂点vとvまでの長さlengthを持つ、DFSをしていく。最大の長さをansとして、length>ansのときansを更新していく。注意点として帰りがけに頂点vを未探索にすることを忘れずに。 n,m=map(int, input().split()) g=[[]for _ in range(n)] C=[[0 for _ in range(n)]for _ in range(n)] for _ in …

atcoder.jp・参考： よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録・やったこと：参考記事の内容をpythonで勉強した。長さがNのリストAをDFSで全探索する。その時の得点(score)が一番高いものがansになる。 #参考：https://drken1215.hatenablog.com/entry/2020/05/04/190252 n,m,q=map(int,input().split()) a=[0 for _ in range(q)] b=[0 for _ in range(q)] c=[0 for _ in range(q)…

競プロで、ロジックの勉強してるときに、分からなくて色々調べたら、 タイトルにある、DFS関数にたどり着いた。 深さ優先探索 というワードの意味が、いまいちピンとこなくて、他のないのかな〜って思うけど、そこが味噌ではないから、まあ、ええかと。。。 調べると、C系言語で書かれた例が見つかった。ただ、自分はPHPを勉強しているのと、C系言語が理解できないので、Chat GPTさんに、php に置換してもらった。それが以下のコード。あと、課金したGPTさんの返答なんで、アプデ前のだとどう返ってくるかは知らん。 あと、このコードに対して、分かりやすく解説して！って投げたら、解説してくれました笑 流石！ …

深さ優先探索はグラフ探索アルゴリズムの一種であり、木構造やグラフ構造の探索に広く使われています。深さ優先探索では、あるノードから始まり、そのノードから伸びる子ノードを優先的に探索していきます。その探索が行き詰まった場合には、一つ前のノードに戻り、別の子ノードを探索していくという方法を繰り返していきます。以下では、Pythonで深さ優先探索を実装する手順を説明します。 深さ優先探索とは 深さ優先探索（Depth-First Search, DFS）とは、グラフ探索アルゴリズムの一つであり、あるノードから始まり、そのノードから伸びる子ノードを優先的に探索していきます。その探索が行き詰まった場合には…

深さ優先探索（Depth-First Search） ある状態からはじめて、遷移できなくなるまで状態を進める。遷移できなくなったら1つ前の状態に戻る。上記はstackのpushとpopで実現できる。このため、深さ優先探索は再帰関数（呼び出し元に戻る）で実装できる場合が多い。 部分和問題（Partial Sum） {a1, a2, ..., an}からいくつか選んだ和がkになるかを判別する。今回は深さ優先探索で各組み合わせの和をすべて求める。a1から順に和に加えないor加えるを決める。このため、以下のような二分木に対して、深さ優先探索を行えば良い。 public class PartialSum…