幅優先探索とは コンピュータの人気・最新記事を集めました - はてな (original) (raw)

幅優先探索

(

コンピュータ

)

【

はばゆうせんたんさく

】

木構造のノードを、根からはじめて、次のような順序でたどる探索方法。
0. キューに根を追加する。
1. キューからノードを一つ取り出し、たどる。その子があれば、キューに追加する。
2. 1. キューが空でなければ 1. を繰り返す。
http://upload.wikimedia.org/wikipedia/commons/b/bc/Breadth-first-tree.png
幅優先探索 - Wikipedia

関連：深さ優先探索

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

関連ブログ

ルクの競プロ部屋•7ヶ月前

競プロ精選 100 問 by C++<幅優先探索>はじめに 今回は幅優先探索の6問をやりました！ 精選100問はこちら！ 28 ALDS_11_C - 幅優先探索 問題はこちらです！ 問題文↓ グラフを与えるので頂点1からの一番短い距離をBFSで求めてください 基本問題でした！ コードは以下のようになりました #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…

#競プロ#精選100問#幅優先探索

ネットで話題

もっと見る

102ブックマーク幅優先探索すら知らない素人がDevQuizで満点を取るまでの話www.slideshare.net

55ブックマーク幅優先探索 | アルゴリズム[Ruby/Python][AOJ 0129]morizyun.github.io

39ブックマーク幅優先探索 - Wikipediaja.wikipedia.org

39ブックマークLevelsモナドを使った幅優先探索の仕組みzenn.dev

36ブックマーク幅優先探索で迷路の最短経路を探すchalow.net

31ブックマークPythonで幅優先探索を実装する - りんごとバナナudomomo.hatenablog.com

26ブックマーク第1回 幅優先探索の基本xtech.nikkei.com

19ブックマークアンカテ(Uncategorizable Blog) - 安倍辞任関連記事を幅優先探索essa.hatenablog.com

18ブックマーク通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】 - あのねノート。ottati.hatenablog.com

関連ブログ

stosasa’s blog•1年前

atcoder ABC317 E - Avoid Eye Contactの勉強atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 参考記事をPythonで実装した。 注意点としてBFSのcontinueする条件は s[nx][ny]!='.' とすると s[nx][ny]='G'(ゴール) のときをスルーしてしまうので一生ゴールにつかなくなる。 from collections import deque h,w=map(int,input().split()) s=[input() for _ in range(h)] #スタート、ゴ…

#Python#AtCoder#AtCoder Beginner Contest#幅優先探索#競技プログラミング

stosasa’s blog•1年前

atcoder ABC309 D - Add One Edgeの勉強atcoder.jp・参考： www.youtube.com・考え方：bfsで解く。1から行ける頂点の距離をdist1、N1+N2から行ける頂点の距離をdist2とする。あとはそれぞれのmaxを取って+1したのが最大の距離になる。 from collections import deque #入力 n1,n2,m=map(int, input().split()) n=n1+n2 g=[[]for _ in range(n)] for _ in range(m): a,b=map(int, input().split()) a-=1 b-=1 g[a].append(b) g[b].appen…

#Python#AtCoder#AtCoder Beginner Contest#BFS#幅優先探索

stosasa’s blog•1年前

atcoder arc C - 器物損壊！高橋君の勉強 ・問題： atcoder.jp・参考： Submission #16162979 - AtCoder Regular Contest 005 AtCoder ARC 005 C - 器物損壊！高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録・0-1BFS： 01-BFSのちょっと丁寧な解説 - ARMERIA・ダイクストラ法： グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube・0-1BFSを使う。壁の有無で0，1を重さとしてBFSするものをいう。ダイクストラ法の重さが0，1になったもので、0のときはdequeの左から入れて1のときは右から入れる。こうすると0の…

#Python#AtCoder#AtCoder Regular Contest#0-1BFS#幅優先探索

stosasa’s blog•1年前

atcoder Darker and Darkerの勉強・問題 atcoder.jp ・参考 AtCoder AGC 033 A - Darker and Darker (緑色, 300 点) - けんちょんの競プロ精進記録 ・考えたこと：DFSかBFSを使うことは分かったが具体的なやり方は思いつかなかった。上の記事を参考にして、スタートを'#'としてbfsをする。'#'からの距離distが最大のものが答えとすれば良いということが分かった。・注意点：pypyで提出してください。 ・実装例： from collections import deque H,W=map(int,input().split()) field=[] for _ in ran…

#AtCoder#atcoder Grand Contest#BFS#Python#幅優先探索

stosasa’s blog•1年前

幅優先探索の問題 atcoder D - Grid Repaintingを解く・問題： atcoder.jp ・参考文献： スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita ・説明：幅優先探索を使ってとく。詳しくは参考文献を参照。プログラムの説明は'#'の数(kabe)とスタートを含むゴールまでの最短距離(dist[gx][gy]+1)を全体(H*W)から引いた値になる。これを素直に実装すればよい。 ・実装例： from collections import deque H,W=map(int,input().split()) field=[] for _ in range(H): field.append(list(input())) sx=0…

#Python#AtCoder#BFS#幅優先探索

stosasa’s blog•1年前

atcoder E - チーズ (Cheese) のpythonでの解答atcoder.jp・注意点：TLEする可能性があるのでPypyで提出してください。・説明：幅優先探索を使ってとく。プログラムの流れはgoalにチーズの位置を入れて、チーズの位置をゴール(gx,gy)、次のループでゴールをスタートにして(sx=gx,sy=gy)幅優先探索をする。また幅優先探索では、for文のはじめで前のループの結果を引き継がないように初期化する必要がある。・実装： from collections import deque H,W,N=map(int,input().split()) field=[] for _ in range(H): field.append(list(…

#Python#BFS#幅優先探索#AtCoder

stosasa’s blog•1年前

pythonでの幅優先探索(BFS) マップが入力で与えられているとき・問題 atcoder.jp・参考： スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita・注意点：参考文献を見れば基本大丈夫だが、スタートとゴールの座標をマイナス1する必要がある。(sx-=1,,,のように)・実装： from collections import deque H,W=map(int,input().split()) sx,sy=map(int,input().split()) gx,gy=map(int,input().split()) #1つ下げる sx-=1 sy-=1 gx-=1 gy-=1 field=[] for _ in range(H): …

#Python#幅優先探索#BFS

stosasa’s blog•1年前

幅優先探索(bfs)のpythonでの実装・参考： BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita・内容：上の記事を参考にpythonでBFSを書いた。queueはcollectionsのdequeのほうが早いらしい。dequeはque=deque() #que.append(i)でappend,que.popleft()で左を取り出してキューから左の要素が消える。 queueはque=queue.Queue() #que.put(i),que.get()で同じことができる。・実装：頂点0からの距離distを求めるもの。 from collections import deque import q…

#Python#BFS#幅優先探索

PyDocument•1年前

Pythonで幅優先探索を実装する方法幅優先探索は、グラフや木構造などのデータ構造で、あるノードから開始して、そのノードから近いノードを順に探索するアルゴリズムです。これは、最短経路を求める問題などに使われます。以下に、Pythonで幅優先探索を実装する手順と具体例を示します。 幅優先探索のアルゴリズム 幅優先探索は、幅優先探索木を作成することによって実装されます。幅優先探索木は、始点ノードからの距離に基づいて、ノードをレベルごとに分類した木構造です。以下に、幅優先探索のアルゴリズムを示します。 始点ノードをキューに入れる。 キューからノードを取り出す。 取り出したノードが目的のノードかどうかを調べる。 取り出したノードから伸びる…

#Python#幅優先探索#アルゴリズム

KCPCブログ•12日前

【ABC373】KCPCブログ第２回はじめに はじめまして、kmmtkm です！読み方をよく訊かれますが、そのまま「けーえむえむ てぃーけーえむ」と読みます。ちなみにTwitter のアカウント名は遠宮歩です。メンバーでは珍しく、人間・環境学研究科に所属しています。 さて、KCPCメンバーが書くブログの第２回です。今週もABCの感想・考えたことを書いていきます。 目次 はじめに 目次 ABC373 A問題 B問題 C問題 D問題 F問題 E問題 コンテスト後 コンテスト結果 ABC373 参加前の私のレートは1204でした。直近２回は緑パフォが続いていて、今回も緑パフォだと緑コーダーに戻ってしまうという怖さがありました。 そして…

プログラミングの備忘録•1ヶ月前

processingの備忘録 -ダイクストラ法-こんにちは。 今回は「ダイクストラ法」を扱います。 前回、幅優先探索と深さ優先探索を実装してみました。 taq.hatenadiary.jp これで単純なグラフや迷路などは最短経路が求められるようになりました。 しかし、エッジも値を持つような、重みつきのグラフなどを対象にはできません。 そんなときに登場するのが「ダイクストラ法」です。 目次 ダイクストラ法とは アルゴリズム 実装 グラフ 地図 まとめ 参考 ダイクストラ法とは ダイクストラ法は、ノード間の距離が 1 ではなく自然数の "重み" を持つようなグラフについて最短経路を求めるアルゴリズムです。 幅優先探索の発展形とも言えるようなもの…

プログラミングの備忘録•1ヶ月前

processingの備忘録 -幅優先探索・深さ優先探索-こんにちは。 今回は「幅優先探索」と「深さ優先探索」を扱ってみます。 以前、迷路をつくったり、解いたり、迷路の形が雷の軌跡のモデルになるらしいと聞いて実際にやってみたりしました。 taq.hatenadiary.jp taq.hatenadiary.jp 1つ目の記事で迷路を解く方法として、行き止まりを埋めていくもの (言わば穴埋め法？) を実装してみました。 そんなある種外道なやり方だけ取りあげて、有名な幅優先探索や深さ優先探索はノータッチでしたので今回やってみます。 はじめてのように書いていますが、改めて読んでみたら雷の軌跡の件で幅優先探索だけやっていたようです。 2年前にちょろっと触れた…

JunKobayashi’s diary•2ヶ月前

ABC368挑戦記（D問題まで）D問題が425点の回における個人的通例を脱し見事4完に成功😎😎😎😎😎😎😎 ※本記事は0-indexedを前提として記載。 ＜A問題＞ ↓問題のページ↓ A - Cut 何だか最近A問題の難易度が上がってきてない・・・？ それはそうとして問題文に書かれた通りの実装をしよう。一番下のカードは\(N - 1\)番目なので、一番下から\(K\)枚を取り出す時、その塊の一番上は\(N - K\)番目である。というわけで、まず\begin{align} A_{N - K}, A_{N - K + 1}, \dotsc , A_{N - 1} \end{align}の順に出力し、その後に\begin{ali…

shibh308’s diary•2ヶ月前

CakeCTF 2023 writeups2023/11/11-2023/11/12に行われた CakeCTF 2023 のupsolve。 一部の問題は既に解いていたが、AlpacaHack に問題が収録されていい機会なので全部解き直すことにした。 Country DB (Web, 246 solves) vtable4b (Pwn, 217 solves) towfl (Web, 171 solves) nande (Rev, 93 solves) simple-signature (Crypto, 88 solves) bofww (Pwn, 75 solves) Cake Puzzle (Rev, 56 solves) Mem…

memo•2ヶ月前

paizaでランクを上げるためにはじめに Pythonの習得からDランク取得まで Cランク取得まで Cランクで要求される内容 重要度についての説明 Bランク取得まで Bランクで要求される内容 A or Sランク取得まで A, Sランクで要求される内容 A, Sランクで要求されるアルゴリズム Q&A "埋めていく"っていうのは過去の問題を全部埋めないといけない？ 何分考えてもどうやって解いたらいいかわからない... 解けなかった問題はどうしたらいい？ おすすめサイト アルゴリズムロジック AtCoder NoviSteps はじめに この記事では、Pythonの言語習得からpaizaのスキルチェックでA or Sランクを取得す…

JunKobayashi’s diary•2ヶ月前

ABC361 D問題発想の根幹にあるのは幅優先探索で、上手く応用できるかを問われている一問といった感触。 ↓問題のページ↓ D - Go Stone Puzzle 問題の状況設定からして、実質的には\((N + 2)\)箇所ある枠を石が動くということなので、以下では入力された\(N\)に対して\(2\)を加算しており、文字列\(S, T\)に対し、右側に2つの空きマスを表す文字（何でもいいがここでは'X'とする）を連結しているという前提で考える。 最大で枠の数は16ということになるが、かなり少ない値なのでまず状態数がどれくらいになるのかを考える。空きマスは必ず2か所が連続していなければならないという制約が付いてい…

FPGA開発日記•3ヶ月前

幅優先探索におけるTop Down方式とBottom Up方式についてグラフアルゴリズムにおける幅優先探索(Breadth Width Search: BFS)というのは、グラフのスタート・ノードから始まって、ノードに隣接するノードを探索してから、さらにそのノードに隣接するノードを探索するというアルゴリズムだ。 グラフアルゴリズムの授業において、最も基本的なアルゴリズムであるものの、その最適化にはいろんな方法があって勉強になる。 例えば、グラフアルゴリズムのベンチマークであるGAPでは、ベンチマークの1種としてBFSが用いられている。 github.com BFSのアルゴリズムの説明について、以下の文献が詳細を説明してくれている： https://arxiv.o…

れとろのメモ置場•3ヶ月前

トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）に参加しました。 結果 A,B,C,D問題の4問正解でした。 久々に4問解けた気がする。E問題は難しかった。 A - Buy a Pen 赤色、緑色、青色のペンが売られているので指定された色以外で安い方の金額を答える問題。 文字列判定で指定された色を識別して、その色以外の2色の内安い小さい方の値段を答える問題。 文字列判定と数値の大小判定が正しく実装できれば解ける問題。 B - Right Triangle 2次元平面上にある三角形の頂点座標が渡されるので、この三角形が直角三角形かどうか…

tapiokaのBMS攻略日記•3ヶ月前

7/13 車校に通う男M1にしてようやく車校に通い始めた。適性検査下手くそ過ぎてあんま理解できんかったけどおもろかったわatcoder.jp茶色適正らしい オワリ

Yuulis.log•3ヶ月前

【AtCoder】ABC 361 D - Go Stone Puzzle | 茶コーダーが解くAtCoderatcoder.jp実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1202 問題概要 個のマスが横一列に並んでおり、左から 個目のマスをマス とする。マス からマス には白か黒の石が置かれており、マス は何も置かれていない。なお、 個のマスの状況は文字列 で表され、 がWのときは白の石、Bのときは黒の石が置かれていることを示す。このとき、「石が2個並んでいる箇所を選び、その2個の石を順序を保って空きマスに移す」という操作を0回以上行って以下の状態にすることが可能か判定し、可能なら操作回数の最小値を求めよ。不可能ならば-1を出力せよ。 マス からマス …

itstaffing エンジニアスタイル•3ヶ月前

プログラミングパズルを使って、普遍的に使えるアルゴリズムを楽しく理解 「楽しいパズルを解くように、アルゴリズムやプログラミングが使えたら……？」 ITエンジニアの無期雇用サービス「BUILDICT」主催にて、関西エリア在住のエンジニアに向けたイベントを実施しました。数理工学を専門にしている大槻兼資さんを講師としてお迎えし、とっつきやすいパズルを用いて、アルゴリズムの基本や応用を理解できるイベントです。本レポートでは、その様子をお届けします。 【講 師】大槻兼資さん1988 年生まれ。2014 年東京大学大学院情報理工学系研究科修士課程修了。修士（情報理工学）。現在、株式会社 NTT データ数理システム顧問、モノグサ株式会社コンテンツアーキテクト。数学や情報科学の…

Yappli Tech Blog•4ヶ月前

GoでJSONから値を探索する時にgojqが便利だったはじめに こんにちは、サーバーサイドエンジニアの中川（@tkdev0728）です。 JSONから特定のキーを使って値を抽出するというユースケースは珍しくないと思います。言語やツールによっていくつかやり方は変わると思うのですが、 今回はリクエスト先と抽出用のキーが動的に変わるのでさまざまなパターンが想定されていました。 Goで抽出を行いたく、探索ロジックを自前で実装しなきゃいけないかなと思ったのですが調べてみるとgojqというライブラリがあることを知り使ってみました。 めちゃくちゃ便利だと思ったので今回はgojqについて紹介してみようと思います。 gojqとは リポジトリはこちら github.…

eijirouの競プロ参加記•4ヶ月前

AHC033 参加記公式ビジュアライザ (Seed=0, Score=70) トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033 お疲れ様でした。 システムテストの得点が 1,971,936,410,473 点で 3 位でした。 問題概要 マスの空間で、5 台のクレーンを操作し、左の搬入口から右の搬出口にコンテナを運ぶ問題です。 詳しくは公式の問題文を参考にしてください。 atcoder.jp 最終提出の方針 ビームサーチをしました。 ビームサーチの 1 ステップは以下の操作です。 1 台のクレーンが、コンテナの場所まで移動してコンテナを掴み、コンテナを運…

FPGA開発日記•4ヶ月前

幅優先探索のハイブリッド方式のアルゴリズムについて勉強幅優先探索(BFS)というのは，有名なグラフアルゴリズムで，その名の通りグラフを同じ距離の順にたどっていくアルゴリズムだ． 以下の資料を参考にして，詳細を掴んでいく． https://mnakao.net/data/2020/HPC175.pdf グラフの直径が小さいというのは，グラフの互いのノードの最大距離が小さいということを意味する． 探索中の頂点の数が非常に大きくなると効率が悪くなるというのは，それぞれの頂点に対して隣接している頂点がすでに訪問済みの可能性が高く，それを何度も確認のために訪問するのは効率が悪いということだと思う． そこで，訪問する数を削減するために，探索の中間の段階でTo…