はじめに

新入生のみなさんご入学おめでとうございます。
今回は競技プログラミングにまつわる話題を話したいと思います。このブログをきっかけに競プロを始めてもらえたら嬉しいです。

幅優先探索

競技プログラミングでよく使うアルゴリズムに幅優先探索というものがあります。頂点と、頂点を結ぶ辺が与えられたグラフで、スタートの頂点からゴールの頂点まで最短何手でたどり着けるか、などの問題をこのアルゴリズムを使って解くことができます。
さっそく問題を解いてみましょう!

問題

番号0からN-1のN個の頂点とM個の辺のグラフがあり、辺は(a、b)のペアでM個与えられ、それぞれ頂点aと頂点bをつなげているとします。最初頂点0にいて、そこから頂点N-1に到達可能か調べてください。
ーーーーーー
辺と頂点の関係をすっきりさせるために隣接リストを使います。
隣接リストではリストのi番目に頂点iと繋がっている頂点を記録します。そうするとリストのi番目を取得することで頂点iから一辺でつながっている頂点の集合を調べることができます。
M個の辺について
・リストのa番目にあるリストにbを追加する
・リストのb番目にあるリストにaを追加する
することで実現できます。

地点0から始めましょう
隣接リストの0列目には頂点0と一辺で繋がっている頂点の集合があります。この頂点らから、また繋がる頂点を調べる、ということを繰り返せば頂点N-1に到達可能か調べられそうです

このとき、次の頂点から今の頂点に帰ることのないように頂点が探索済みかのリストを取っておきましょう

また、調べる頂点を記録するリストが別に必要そうです、そこで調べる頂点を”キュー”で記録しておきましょう
キューはリストの最初の要素の取り出しとリストの末尾に要素を追加することに注目し、それを高速に行うことができます、今回の頂点を順に調べる処理に向いていますね

この問題を解きます
使用するのは
頂点が探索済みか記録するリストD
調べる頂点を記録したキュー
隣接リスト
です

Dの全ての要素は”未探索”で初期化しておきます

①キューに0を追加
②D[0]を”探索済み”とする
③キューの最初の一要素を取り出し、それをxとする
④xに隣接する(一辺でつながっている)全ての頂点について
ーーすでに探索済みならば、無視
ーー未探索なら、調べる頂点としてキューに追加し、Dのその頂点を”探索済み”とする
⑤キューが空になるまで③、④を繰り返す
⑥D[N-1]が答え

キューはcollections dequeで使えます

from collections import deque

##入力例
N = 6
M = 6
0,3
0,1
1,2
3,1
4,2
5,4
##

N = int(input())
M = int(input())

G = [[] for i in range(N)]

##隣接リストの作成
for i in range(M):
  a,b = map(int,input().split())
  G[a].append(b)
  G[b].append(a)

###G
G = [[1,2],
     [0,2,3],
     [1,4],
     [0,1],
     [2,5],
     [4]]
###

D = ["未探索" for _ in range(N)]
q = deque()

q.append(0)
D[0] = "探索済み"

while q:
  x = q.popleft()
  for next_node in G[x]:
    if D[next_node] == "未探索":
      q.append(next_node)
      D[next_node] = "探索済み"

if D[N-1]=="探索済み":
  print("到達可能")
else:
  print("到達不可能")

このようなアルゴリズムでこの問題を解くことができます

問題

番号0からN-1のN個の頂点とM個の辺のグラフがあり、辺は(a、b)のペアでM個与えられ、それぞれ頂点aと頂点bをつなげているとします。一辺を通って繋がる頂点に移動するとき一手として、最初頂点0にいて、そこから頂点N-1に最短何手で到達可能か調べてください
ーーーーーー
今回は先ほどの問題に最短何手で到達するか、という要素が加わりました

そこで、その頂点が到達可能か記録するリストをその頂点が最短何手で到達可能か記録するリストに変更します

このようなリストでスタート0を0手で記録しておき、次の頂点の最短手数＝今の頂点の最短手数+1、と記録していきます

幅優先探索はキューに追加されて一番古い要素を取り出していくため、まるでこぼした水が広がるように頂点を調べていきます、今回の一辺の移動が一手の時は自然と調べる順=最短手順になります

この問題を解いていきます
使用するのは
頂点が最短何手で到達可能か記録するリストD
調べる頂点を記録したキュー
隣接リスト
です

Dの全ての要素を”INF”で初期化しておきます
Dの要素が”INF”のとき未探索であり、何らかの数値のとき探索済みということです

①キューに0を追加
②D[0]を”0″とする
③キューの最初の一要素を取り出し、それをxとする
④xに隣接する全ての頂点について
ーーDの値が何らかの数値なら、無視
ーーDの値が”INF”なら、調べる頂点としてキューに追加し、Dのその頂点の値を(D[x]+1)とする
⑤キューが空になるまで③、④を繰り返す
⑥D[N-1]が答え

from collections import deque

##入力例
N = 6
M = 6
0,3
0,1
1,2
3,1
4,2
5,4
##

N = int(input())
M = int(input())

G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,input().split())
  G[a].append(b)
  G[b].append(a)

###G
G = [[1,2],
     [0,2,3],
     [1,4],
     [0,1],
     [2,5],
     [4]]
###

D = ["INF" for _ in range(N)]
q = deque()

q.append(0)
D[0] = "0"

while q:
  x = q.popleft()
  for next_node in G[x]:
    if D[next_node] == "INF":
      q.append(next_node)
      D[next_node] = D[x]+1

if D[N-1]=="INF":
  print("到達不可能")
else:
  print(D[N-1])

これでこの問題が解けました。

おわり

今回は幅優先探索について解説してみました
ここに辺のコストなんかが加わるとさらに複雑になっていきます。競プロやってみてね!