グラフの問題について
- ABCの問題ではD問題でグラフの問題が出題されることが多い。解けるようになると一気に4完に近づくことができる。
グラフとは？用語解説
- 夏休み講習会の内容をつかいます。 https://members.maximum.vc/assets/per-year/2024/graph-intro.pdf
BFS(幅優先探索)
-
幅優先探索は、与えられたノードから近い順に探索するアルゴリズム。
-
グラフの最短経路を求めたい時によく使われる。
-
キューを使って実装する。
-
キューに始点を入れ、キューが空になるまで以下の処理を繰り返す。
- キューから要素を取り出す。
- 取り出した要素に隣接する頂点をキューに入れる。
-
仕組みについては以下の記事がわかりやすい。 https://qiita.com/drken/items/996d80bcae64649a6580
例題
ヒント
- 先ほどの記事(https://qiita.com/drken/items/996d80bcae64649a6580)内のBFSテンプレを書き換えると解くことができます。
- どう動いているのか確認しながら解いてみてください。
解答例
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
int main() {
// 頂点数
int n; cin >> n;
// グラフ入力受取
vector<vector<int>> G(n);
rep(i, n) {
int u,k; cin >> u >> k;
rep(j, k) {
int c; cin >> c;
G[u-1].push_back(c-1);
}
}
// BFS
vector<int> dist(n, -1); // 全頂点を「未訪問」に初期化
queue<int> que;
// 初期条件 (頂点 0 を初期ノードとする)
dist[0] = 0;
que.push(0); // 0 を橙色頂点にする
// BFS 開始 (キューが空になるまで探索を行う)
while (!que.empty()) {
int v = que.front(); // キューから先頭頂点を取り出す
que.pop();
// v から辿れる頂点をすべて調べる
for (int nv : G[v]) {
if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない
// 新たな白色頂点 nv について距離情報を更新してキューに追加する
dist[nv] = dist[v] + 1;
que.push(nv);
}
}
// 結果出力 (各頂点の頂点 0(+1) からの距離を見る)
rep(v,n) cout << v+1 << " " << dist[v] << endl;
}
演習問題
DFS(深さ優先探索)
-
深さ優先探索は、与えられたノードから可能な限り深く探索するアルゴリズム。
-
スタックを使って実装する。
-
スタックに始点を入れ、スタックが空になるまで以下の処理を繰り返す。
- スタックから要素を取り出す。
- 取り出した要素に隣接する頂点をスタックに入れる。
-
仕組みについては以下の記事がわかりやすい。
例題
解答例
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int H, W;
vector<vector<char>> grid; // 街の格子状の区画
vector<vector<bool>> visited; // 訪問済みの区画
int sx, sy, gx, gy; // 家(s)の位置と魚屋(g)の位置
vector<int> dx = {1, -1, 0, 0}; // 東西南北の移動
vector<int> dy = {0, 0, 1, -1}; // 東西南北の移動
// スタックを使ったDFS
bool dfs_iterative(int startX, int startY) {
stack<pair<int, int>> stk; // スタックを使って探索
stk.push({startX, startY}); // 初期位置をスタックに追加
visited[startY][startX] = true;
while (!stk.empty()) {
auto [x, y] = stk.top(); // 現在の位置を取得
stk.pop(); // スタックから取り出す
// 魚屋に到達した場合
if (x == gx && y == gy) return true;
// 東西南北に移動する
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 移動先が街の範囲内かつ、道または魚屋であり、まだ訪問していない場合
if (nx >= 0 && nx < W && ny >= 0 && ny < H && !visited[ny][nx] && grid[ny][nx] != '#') {
visited[ny][nx] = true; // 訪問済みとしてマーク
stk.push({nx, ny}); // 新しい位置をスタックに追加
}
}
}
return false; // 魚屋にたどり着けなかった場合
}
int main() {
cin >> H >> W;
grid.resize(H, vector<char>(W));
visited.resize(H, vector<bool>(W, false));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> grid[i][j];
if (grid[i][j] == 's') {
sx = j; sy = i; // 家(s)の位置を記録
}
if (grid[i][j] == 'g') {
gx = j; gy = i; // 魚屋(g)の位置を記録
}
}
}
// スタックを使ったDFSで探索開始
if (dfs_iterative(sx, sy)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}