ALDS1 11C 幅優先探索

この記事で使うアルゴリズム

幅優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja

この問題は幅優先探索を用いて解くことができます。

コード

depthは距離の記録であり、訪問済みかどうかの判定にも用います。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import queue
N = int(input())

adj = [[]for i in range(N+1)]
depth = [-1] * (N+1)
for n in range(1,N+1):
V = list(map(int,input().split()))
for v in V[2:]:
adj[n].append(v)

q = queue.Queue()
q.put((1,0)) # 番号、深さ
while(not q.empty()):
x, d = q.get()
if depth[x] != -1:
continue
depth[x] = d
for next in adj[x]:
if depth[next] == -1:
q.put((next,d+1))

for i in range(1,N+1):
print(i,depth[i])

記事情報

  • 投稿日:2020年5月18日
  • 最終更新日:2020年5月18日