AtCoder NoviStepsを埋めてみる(24) スタック：かっこ列を扱うの続きです。今回は幅優先探索（BFS）です。
幅優先探索は、スタートから近い頂点から順に探索していくアルゴリズムです。辺の重みが同じグラフであれば始点からゴールまでの最短手数を調べるときに採用されるアルゴリズムです。迷路の最短経路や最小手数の移動問題でよく使われます。
C – 幅優先探索
問題の概要
二次元盤面上の迷路を解くために必要な最小移動手数を求めよ。
幅優先探索がなにかは問題が掲載されているページに詳しく書かれています。あとは書かれているとおりにコーディングするだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class Program { static void Main() { int[] rc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] syx = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] gyx = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int R = rc[0]; int C = rc[1]; int sy = syx[0] - 1; int sx = syx[1] - 1; int gy = gyx[0] - 1; int gx = gyx[1] - 1; char[][] grid = new char[R][]; for (int i = 0; i < R; i++) grid[i] = Console.ReadLine().ToArray(); int[,] dists = new int[R, C]; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) dists[r, c] = int.MaxValue; } Queue<(int, int)> q = new Queue<(int, int)>(); dists[sy, sx] = 0; q.Enqueue((sy, sx)); int[] dx = [0, 0, 1, -1]; int[] dy = [1, -1, 0, 0]; while (q.Count > 0) { var cur = q.Dequeue(); for (int i = 0; i < 4; i++) { int ny = cur.Item1 + dy[i]; int nx = cur.Item2 + dx[i]; if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue; if (grid[ny][nx] == '#') continue; int n_dist = dists[cur.Item1, cur.Item2] + 1; if (dists[ny, nx] > n_dist) { dists[ny, nx] = n_dist; q.Enqueue((ny, nx)); } } } Console.WriteLine(dists[gy, gx]); } } |
044 – Shortest Path 1
問題の概要
N 頂点 M 辺の無向グラフが与えられる。
頂点 1 から頂点 k の最短経路長をそれぞれ求めよ。ただし、移動不可能な場合は -1 を出力せよ。
頂点 1 を起点に幅優先探索を 1 回やればそれ以外の頂点への最短経路長を求めることができるので、その結果を出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; G[a].Add(b); G[b].Add(a); } int[] dists = new int[N]; Array.Fill(dists, int.MaxValue); Queue<int> q = new Queue<int>(); dists[0] = 0; q.Enqueue(0); while (q.Count > 0) { int cur = q.Dequeue(); foreach (var next in G[cur]) { if (dists[next] > dists[cur] + 1) { dists[next] = dists[cur] + 1; q.Enqueue(next); } } } for (int i = 0; i < N; i++) Console.WriteLine(dists[i] < int.MaxValue ? dists[i] : -1); } } |
Bfsメソッドを定義しておくと便利かもしれません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Program { static void Bfs(List<int>[] G, int start, int[] dists) { Queue<int> q = new Queue<int>(); dists[start] = 0; q.Enqueue(start); while (q.Count > 0) { int cur = q.Dequeue(); foreach (var next in G[cur]) { if (dists[next] > dists[cur] + 1) { dists[next] = dists[cur] + 1; q.Enqueue(next); } } } } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; G[a].Add(b); G[b].Add(a); } int[] dists = new int[N]; Array.Fill(dists, int.MaxValue); Bfs(G, 0, dists); for (int i = 0; i < N; i++) Console.WriteLine(dists[i] < int.MaxValue ? dists[i] : -1); } } |
C – Count Connected Components
C – Count Connected Components
問題の概要
N 頂点 M 辺の無向グラフが与えられる。
グラフに含まれる連結成分の個数を求めよ。
最初に見つかった未訪問の頂点から辺をたどって移動できる頂点にすべて訪問済みのフラグを立てます。この処理が終わったら別の未訪問の頂点を探し、同様の処理をおこないます。この処理を何回繰り返すことができたかを数えます。これが連結成分の個数となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Program { // Bfs(List<int>[] G, int start, int[] dists) は上記と同じ static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; G[a].Add(b); G[b].Add(a); } int[] dists = new int[N]; Array.Fill(dists, int.MaxValue); int ans = 0; for (int i = 0; i < N; i++) { if (dists[i] == int.MaxValue) { Bfs(G, i, dists); ans++; } } Console.WriteLine(ans); } } |
C – Straw Millionaire
問題の概要
N 種類のアイテムがある。はじめはアイテム 1 のみ持っている。
M 人の友達がいて友達 i にアイテム A[i] を渡すと、アイテム B[i] をもらうことができる。
手に入れることのできるアイテムはアイテム 1 を含めて何種類あるか求めよ。
最初に N 個の頂点を定義します。「アイテム A[i] を渡すと、アイテム B[i] をもらうことができる」は「A[i] から B[i] に移動できる」と考えます。
頂点 1 から移動可能な頂点が何個あるかを調べます。これが手に入れることのできるアイテムの種類数となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class Program { // Bfs(List<int>[] G, int start, int[] dists) は上記と同じ static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; G[a].Add(b); } int[] dists = new int[N]; Array.Fill(dists, int.MaxValue); Bfs(G, 0, dists); int ans = 0; for (int i = 0; i < N; i++) { if (dists[i] < int.MaxValue) ans++; } Console.WriteLine(ans); } } |
