[白俊]2606号-ウイルス
📩 ソース
質問する
新型ウイルスワームウイルスはネットワークを通じて伝播する.1台のコンピュータがワームウイルスに感染した場合、ネットワークに接続されているすべてのコンピュータがワームウイルスに感染します.
例えば、<図1>に示すように、7台のコンピュータがネットワークに接続されているとする.1番のコンピューターがワームウイルスに感染した場合、ワームウイルスは2番と5番のコンピューターを経て3番と6番のコンピューターに伝播し、2、3、5、6の4台のコンピューターがワームウイルスに感染する.しかし、4番と7番は1番とネットワーク接続がないため、影響を受けません.
ある日、1番のパソコンがワームウイルスに感染した.コンピュータの数とネットワーク上の情報が相互に接続されている場合は、コンピュータを介してワームウイルスに感染したコンピュータの数を出力するプログラムを作成します.
入力
最初の行はコンピュータの数を示します.パソコンの数は100以下で、1台あたり1番から順番に番号をつけます.2行目は、ネットワークに直接接続されているコンピュータペアの数を示します.次に、ネットワークに直接接続された各行の1対のコンピュータの番号ペアが与えられる.
しゅつりょく
1番コンピュータがワームウイルスに感染した場合、1番コンピュータを介してワームウイルスに感染したコンピュータの数を1行目に出力する.
👉 の意見を打診
from collections import deque
def bfs():
q = deque([1])
visited[1] = 1
cnt = 0
while q:
v = q.popleft()
for i in lst[v]:
if not visited[i] and i != 0:
visited[i] = 1
q.append(i)
cnt += 1
return cnt
computer = int(input())
n = int(input())
lst = [[0]] * (computer+1)
visited = [0] * (computer+1)
for _ in range(n):
idx, val = map(int, input().split())
if lst[idx] == [0]:
lst[idx] = [val]
else:
lst[idx] = lst[idx] + [val]
if lst[val] == [0]:
lst[val] = [idx]
else:
lst[val] = lst[val] + [idx]
print(bfs())
Reference
この問題について([白俊]2606号-ウイルス), 我々は、より多くの情報をここで見つけました https://velog.io/@letgodchan0/백준-2606번-바이러스テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol