幅優先探索に関するカテゴリーです。

AtCoder, グラフ理論, 幅優先探索

問題方針

幅優先探索で迷路を解くような感じで考えます。始点 \( 1 \) から幅優先探索を行い、到達した部屋の道しるべは、直前に来た部屋となります。隣接リストを作成し、到達した部屋のフラグを管理することで探索を行います。

コード ...

AtCoder, グラフ理論, 幅優先探索, 探索

問題方針

良くある迷路の探索のアルゴリズムを使って、全探索を行います。ここでは、全ての道となっているマスから幅優先探索を行い、到達可能なマスの最短距離を求めます。

コード

 

AOJ, グラフ理論, 幅優先探索, 探索

問題方針

各生徒をノードに見立てて、隣接リストを構築します。生徒 \( i \) が所属している部活動を \( g_i \) とし、所属が未確定のときを \( g_i = 0 \) とします。生徒 \( a, b \) が同じ部活動に所 ...

AtCoder, グラフ理論, 幅優先探索, 探索

問題方針

必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使い ...

AtCoder, グラフ理論, 幅優先探索, 探索

問題方針

座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。

グラフ

各座標をグラフの頂点として、\ ...

AtCoder, 幅優先探索, 探索

問題方針幅優先探索

頂点 \( 1 \) から幅優先探索を行って全ての頂点のカウンターの値を計算します。そのために、頂点 \( i \) が最初のカウンターの値をあらかじめ計算します。最初のカウンターの値とは、ある頂点 \( u \) ...

AtCoder, 幅優先探索, 探索

問題方針ステップ数が \( 3 \) の最短距離の探索

例えば、ステップ数が \( 3 \) の最短経路の探索では、スタート地点から \( 3 \) ステップ目で到達可能な頂点を距離 \( 1 \) で到達可能な頂点とします。また、この ...

AOJ, 幅優先探索, 探索

問題方針幅優先探索

チーズは硬さ \( 1 \) から \( N \) まで順番にとる必要があるので、\( 1 \) から \( 2 \) までの最短距離を計算し、次に \( 2 \) から \( 3 \) までの最短距離を計算するよう ...

CSA, 幅優先探索, 探索

問題問題の意図

頂点数が \( N \) 個で辺の数が \( M \) 本の無向グラフが与えられます。始点 \( S \) から終点 \(A, B \) への最短経路において、同じ辺を通る長さの最大値を答えます。また、辺の重みは \( ...