木構造のノードを、根からはじめて、次のような順序でたどる探索方法。 0. スタックに根を追加する。 1. スタックからノードを一つ取り出し、たどる。その子があれば、スタックに追加する。 2. 1. スタックが空でなければ 1. を繰り返す。 深さ優先探索 - Wikipedia
関連:幅優先探索
こんにちは。倉内です。ある程度プログラミングの基本を学び終えた方の中には、アルゴリズムや数学的知識を深めたいという方もいらっしゃると思います。paizaラーニングで公開している、プログラミング練習問題を集めた「レベルアップ問題集」では、アルゴリズムに関する問題集も多くご用意しています。解答コード例や解説を誤用している問題も多数あるので、「アルゴリズムに興味はあるけど難しそうだし…」という方もぜひ挑戦してみてください。今回はその中からグラフを扱った「グラフ構造の入力メニュー」「木のメニュー」をご紹介します。「グラフってそもそもなに…?」という方向けの説明もありますのでぜひ参考にしてみてください。…
こんにちは、鈴です。 今回は、基本的なアルゴリズムの一つである深さ優先探索についての備忘録です。 アルゴリズムをご紹介した後、Pythonでの実装例を用いて解説を行っていきます。 前回の記事はこちらから↓ riririririn.hatenablog.com では早速行ってみましょう。 深さ優先探索とは 基本 再帰関数による探索 スタックによる探索 Pythonによる実装例 まとめ 余談 深さ優先探索とは 深さ優先探索は、グラフや木構造を探索するための基本的なアルゴリズムの一つです。 木の根にあたる部分からスタートし、それ以上進めない行き止まりの地点まで試行を繰り返し、行き止まりになったらまだ…
AtCoder版!蟻本の深さ優先探索で類題としてあげられているAOJ 1160 How Many Islands?をPythonで解いていきます。 (function(b,c,f,g,a,d,e){b.MoshimoAffiliateObject=a;b[a]=b[a]||function(){arguments.currentScript=c.currentScript||c.scripts[c.scripts.length-2];(b[a].q=b[a].q||[]).push(arguments)};c.getElementById(a)||(d=c.createElement(f),d…
AtCoder版!蟻本の深さ優先探索で類題としてあげられているARC037 BをPythonで解いていきます。 DFSを使ってグラフの連結成分に閉路があるか判別していきます。 (function(b,c,f,g,a,d,e){b.MoshimoAffiliateObject=a;b[a]=b[a]||function(){arguments.currentScript=c.currentScript||c.scripts[c.scripts.length-2];(b[a].q=b[a].q||[]).push(arguments)};c.getElementById(a)||(d=c.crea…
AtCoder版!蟻本の深さ優先探索で類題としてあげられているARC031 BをPythonで解いていきます。 再帰関数を使用して解いています。 (function(b,c,f,g,a,d,e){b.MoshimoAffiliateObject=a;b[a]=b[a]||function(){arguments.currentScript=c.currentScript||c.scripts[c.scripts.length-2];(b[a].q=b[a].q||[]).push(arguments)};c.getElementById(a)||(d=c.createElement(f),d.…
AtCoder版!蟻本の深さ優先探索で類題としてあげられているATC001 AをPythonで解いていきます。 深さ優先探索(DFS)は初めて見たとき難しく感じましたが、何問か解くとイメージがわいてきました。 理解しないと使いこなせないと思いますので頑張って取り組んでいきます。 (function(b,c,f,g,a,d,e){b.MoshimoAffiliateObject=a;b[a]=b[a]||function(){arguments.currentScript=c.currentScript||c.scripts[c.scripts.length-2];(b[a].q=b[a].q|…
新年あけましておめでとうございます!!(おそっ)今日も "初中級者が解くべき過去問精選 100 問" を解いていきたいと思います! 精選100問って何? 過去の記事についてはこちら!! 全探索シリーズ 第1回:全列挙 第2回:工夫して通り数を減らす全列挙 第3回:ビット全探索 第4回:順列全探索 第5回:二分探索 深さ優先探索 24. Depth First Search 25. How Many Islands? 26. D - Ki 27. D - 薄氷渡り 最後に 精選100問って何? 記事はこちら! qiita.com こんなに丁寧にまとめてくださっている e869120 さんには本当…
はじめに 深さ優先探索とは 実装例 再帰を利用した深さ優先探索 おわりに 参考 はじめに こんにちは.talosです.今回は深さ優先探索について説明します.初心者でもわかるように簡潔に書いているので,初心者中の初心者の方にもおすすめです.幅優先探索はこちら talosta.hatenablog.com 深さ優先探索とは 深さ優先探索はグラフの探索方法の1つです.できる限り奥まで探索して,行き止まりになったら分岐点まで戻って探索を繰り返す方法です.例えば,あなたが部屋でスマホをなくしたとします.ある隣の部屋からなるべく奥の部屋まで探して,見つからなければ最初の部屋に戻り,別の隣の部屋からなるべく…
ABC263にて、C問題が解けませんでした。 atcoder.jp (↓無茶苦茶に実装しようとして結局実装しきれなかったもの) atcoder.jp 上記ゴリ押し実装の修正も試みたものの、どんどん肥大化してバグを取り切れませんでした・・・ 仮に次に同じ問題が出たときにもうまく対応できる気がしなかったため、解説を確認して解くことにしました。 いくつかある解説の中では、↓の深さ優先探索で解く方法が比較的実装量も少なく、自分の経験値的にも理解しやすかったのでこちらを選択しました。 atcoder.jp ただ自分の力量だと単純に再帰しているだけに見えてしまい、上限値の処理をどこでしてるのかが分からなか…
こんにちは、osumi_kyopuroです。 今回の記事は私が緑コーダーになるためにやったことについて書きました。参考に出来ることはあまりないかもしれませんが読んでいただけると幸いです。 自己紹介 競プロを始めたきっかけ 緑コーダーになるためにやったこと 最後に atcoder.jp osumiのページ 自己紹介 名前:osumi_kyopuro 年齢:22歳 最終学歴:現役で室蘭工業大学 情報電子工学系学科卒業 職業:Web Application Engineer 会社:都内アプリ開発会社(上場) 競プロを始めたきっかけ 競プロを始めるきっかけになった理由として二つあります。 一つ目はコン…
ストーリー 「このネジを外せば、この部分がとれるのかな?」 フタを外しました。 1* 2 1 2 3 1* 1* 2 1 「なんだろうね……この数字は?」 フタを外しました。 0 1 1* 1 2 1 1* 1 0 「あっ、また数字の羅列!」 「この数字が穴の位置を示している、ということかな?」 フタを外しました。 2 3 2 2 2 4 3 2 1 1 2 2 3 2 2 2 2 1 2 2 3 3 3 3 1 2 4 3 3 3 5 4 2 2 2 3 2 4 3 3 3 4 4 5 5 6 6 5 4 1 2 4 3 3 3 4 4 2 4 3 5 4 5 4 2 4 4 5 5 6 8…
ABC233 C - Product atcoder.jp 組み合わせは深さ優先探索だって言ってんだろ. あと関数内でグローバル変数にアクセスするときは,globalをつける必要があることを学んだ.(母語()がC言語なので,しばらくわけわからなくて悩んだ.) ans = 0 def dfs(pos, product): global ans if pos == N: if product == X: ans += 1 return for i in range(1,La[pos][0]+1): dfs(pos+1, product*La[pos][i]) N, X = list(map(int…
アルゴ式(beta版)の「グラフアルゴリズム」4章:深さ優先探索 (DFS)からの出典です。 algo-method.com アルゴ式とは... >・プログラミングや情報科学をコツコツ学べる「教科書」 >・学んだ内容をゲーム感覚で大量に実践できる「練習問題」 >の2つで構成される、Web上で完結した学習コンテンツです。 C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS) 僕が作成、提出したコードは、以下のとおりです。 Q3. 深さ優先探索 algo-method.com /* アルゴ式(beta版): C++による「グラフアルゴリズム」4章:深さ優先探索 (DFS) Q3. 深さ…
Atcoder 競プロ典型 90 問 026 - Independent Set on a Tree(★4) 問題 atcoder.jp 方針 隣り合う頂点が異なるように2色に塗り分ける 木だから閉路がない → 必ず上記が可能 深さ優先探索ですべての頂点に交互に色を塗れば良い。 色の片方から N/2 個 取り出して表示すれば良い 解答 open Core open Printf (* open Num *) (* open IterLabels *) let id x = x let si _ = Scanf.scanf " %d" id let si2 _ = Scanf.scanf " %…
atcoder.jp A 2N そのまま解く。2の累乗だからビット左シフトで解ける。 open Core open Printf (* open Num *) (* open IterLabels *) let id x = x let si _ = Scanf.scanf " %d" id let si2 _ = Scanf.scanf " %d %d" (fun x y -> x, y) let si3 _ = Scanf.scanf " %d %d %d" (fun x y z -> x, y, z) let sc _ = Scanf.scanf " %c" id let ss _ = …
AbudoriLab.です。 今回は経路計画の記事第二弾として、ダイクストラ法について説明します。 第一弾として幅優先探索と深さ優先探索について説明した記事はこちらです: www.abudorilab.com 【第一弾のあらすじ】 ・基礎的な経路計画の方法として、幅優先探索と深さ優先探索を紹介しました。 ・深さ優先探索では最良経路を得られると限らないので、幅優先探索を使うべきであることを示しました。 ・しかし、幅優先探索も最良経路を求められるのはマス目の重みが平等な地図に限られるため、マス目の重みが異なる地図ではダイクストラ法などの別のアルゴリズムを用いるべきであることを説明しました。 それで…
あたしって,ほんとバカ. ABC256 C Filling 3x3 array atcoder.jp 3X3の各マスを安直に全探索すると,最悪309回for文を回すことになってTLEする. a b c d e f g h i 今回の問題は,a,b,d,eが決まれば,c,f,g,h,iが自動的に決まる. c = h1 - (a + b) f = h2 - (d + e) g = w1 - (a + d) h = w2 - (b + e) i = h3 - (b + e) = w3 - (c +f) a,b,d,eを4重のfor文で全探索して,c,f,g,hを求め,h3 - (b + e) == …
はじめに 最近はAtCoderという競技プログラミングサイトで遊んでいます。AtCoderは豊富に過去問があり、それらがまとまっているAtCoder Problemsというサイトにお世話になっています。AtCoder ProblemsのサービスとにはBoot Camp for Beginnersという、AtCoderの教育的な過去問を解くことができるサービスがあります。全300問で100問ごとにEasy、Normal、Hardと難易度が別れており、それぞれ灰、茶、緑diffが中心の問題となり、Hardの後半から水diffが混ざってきます。 今日はこれを完走したよ!というお話です。 Boot C…
アルゴリズムを学ぶのにPythonの学習も兼ねてPythonで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ)作者:辻真吾講談社Amazonを参照していく。 前回 power-of-awareness.com 前回 6. グラフ構造 6.4 幅優先探索 6.4.3 深さ優先探索とスタック 6.5 最短距離を求める 6.5.1 グラフの最短距離 6.5.2 ダイクストラ法 6.5.3 ダイクストラ法の計算量 次回 6. グラフ構造 ヒトのつながりを表現する手段であるグラフ理論に基づくグラフ構造が利用し得る。 6.4 幅優先探索 6.4.3 深さ優先探索とスタック 深さ優先探索は調べ…
こんなもん要はただのスライドパズルなので探索かければいけるやろ 趣旨 方針 IDA*実装 盤面の表現 タイルをスライドするとは より効率的に配列を表現する方法 評価値 ループ回避 出力形式 IDA*実行1 IDA*実行2 解についての考察1 解についての考察2 さらなる短縮へ BFS おわりに おわらせない 双方向BFS 双方向BFS実行 おわり ソースコード IDA* BFS 双方向BFS 趣旨 6人の壁画は61手解法(http://homentosu.blog.fc2.com/blog-entry-71.html)が知られているが、かなり人間的にわかりやすい操作をしている。これが最適でない…
アルゴリズムを学ぶのにPythonの学習も兼ねてPythonで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ)作者:辻真吾講談社Amazonを参照していく。 前回 power-of-awareness.com 前回 6. グラフ構造 6.1 グラフの基礎 6.2 グラフを表現するデータ構造 6.3 連結グラフにおける探索 6.4 幅優先探索 6.4.1 キュー 6.4.2 キューを用いた幅優先探索 次回 6. グラフ構造 ヒトのつながりを表現する手段であるグラフ理論に基づくグラフ構造が利用し得る。 6.1 グラフの基礎 グラフは頂点(vertex)/節点(nodel)と辺(edg…
1年早い 月曜深夜、空気階段の踊り場をリアタイした。内容は踊り場モノマネ王座決定戦。深夜近所迷惑にならないよう爆笑してた(特にかたまりの中田英寿)。面白かったんだけどそれ以上にビックリしたのが、前回の大会から1年経ってたこと。去年のやつはタイムフリーで聞いて、ちょうど学校帰りに大学に募集要項取り寄せるために切手を買いに行ってる最中だったのも覚えてる。「もう1年なのか…」なんて思って、日付感覚の短っぷりにびっくりしてた。 上島竜兵が亡くなった 12日水曜昼前、いつものように堕落した起床をした。スマホを開くと、昨晩寝る前に聞き流してたYouTubeが開きっぱになっていた。ふと最新動画を見ると「上島…
ABC254でようやく緑色になりました.Twitterでよく見る入◯記事を自分も書きたいと思ってたので書きました.文章かくの得意じゃないので見苦しいとは思いますが,一度開いたなら責任持って頑張って最後まで読んでください.絶対. 自己紹介 Atcoderはgloって名前でやってます.Twitterは窒化イットリウム(@tikka_tika_ 競プロの話はほとんどしないのでフォロー非推奨)です. 20歳の大学三年生で電気通信大学の情報数理工学プログラムに所属しています.(情報数理工学って漢字だけでめちゃかっこいいのに,プログラムで台無しだから情報数理工学科にしてほしい) 競プロは確か高校2年生の冬…