【ABC168 D】「.. (Double Dots)」を解く【Python3】

コンテスト一覧へ

 

N個の部屋とM本の通路がある洞窟の、それぞれの部屋に配置する道しるべの置き方を求める問題です。

提出
from collections import deque

n, m = map(int, input().split())
ab = [[] for i in range(n+1)]
 
for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
 
ans = [-1]*(n+1)
que = deque([1])
 
while que:
    q = que.popleft()
    for i in ab[q]:
        if ans[i] == -1:
            que.append(i)
            ans[i] = q
 
print("Yes")
 
for i in range(2,n+1):
    print(ans[i])

BFS(幅優先探索)を用いて解くのですが、その説明は他のサイトにお任せして、今回のコードでどのような処理をしたかを説明します。

 

まず、abというリストを作成して、辺で繋がっているa,b同士を代入します。

入力例1の場合、for文の後にabを出力すると、

ab = [[], [2], [1, 3, 4], [2, 4], [3, 2]]

というリストになっています。

ab[1] = [2]

ab[2] = [1,3,4]

ですね。1は2と繋がっており、2は、1,3,4と繋がっていることがを入力から代入したためです。

 

次に最後に出力する答えのリスト「ans」の「n+1」個の要素に「-1」を代入します。

今回は、collectionsモジュールの「deque」を使用します。

これを使うことで、先頭の要素を取得・削除する際に、時間コストを少なくすることができます。

que = deque([1])

というリストを作っておいて、先頭の文字列を取得・削除(popleft()を使用)します。

以下の部分のコードを見てください。

while que:
    q = que.popleft()
    for i in ab[q]:
        if ans[i] == -1:
            que.append(i)
            ans[i] = q

que.popleft() の最初の取得は1です。

ab[1]には[2]が入っており、ans[2] = -1 です。

ですので、queの最後に2を加え、ans[2]に「1」を代入しています。

次の取得は2です。

ab[2]には [1,3,4]が入っているため、一つずつ判定します。

ans[1]に2が代入されてしまいますが、出力には関係ないので無視します。

ans[3] , ans[4]に2を代入します。

 

ここで、queには[1,3,4]が入っています。

その次の取得は再び1ですが、ans[2] = 1 であるため、何も変化せず終わります。

3,4 に関しても同様に変化せず、新しい要素がqueに加わるわけではないので、空リストになり、ループから抜け出します。

 

このとき「ans」は、

ans = [-1, 2, 1, 2, 2]

であるので、3つ目の要素から順番に出力します。

その前に「Yes」を出力するのを忘れないように。今回、答えが「No」になるパターンは存在しないため、場合わけは不要です。

【ABC168】解説記事リスト

コンテスト一覧に戻る

2 COMMENTS

神田 裕也

とても分かりやすい良心的な記事を、ありがとうございます。
コードの詳細な説明が充実していて、大変、勉強になります。
自分は、やっと茶色になったばかりです。10か月掛かりました(笑)
Dは ほとんど解けません。解説して頂いた記事を読んで、
「どうしたら、この解法を思いつくのだろう」と不思議に思う
ことがあります。その辺も、教えて頂ければ助かります。
今後とも、よろしく、お願いします。感謝しています。
追伸:最短経路の長さを求めないBFS、面白いですね。

返信する
巻き貝

上の方と同じく、具体的でわかりやすい解説だと思いました。
慣れている人だとコードを読めば処理内容が自然に想像できるのかもしれませんが、茶帯の自分にはちょっと脳への負荷が大きくて……(笑)
参考にさせていただきます。

返信する

コメントを残す

メールアドレスが公開されることはありません。