[アルゴリズム]BOJ 2606ウイルス

[BOJ]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
from sys import stdin
N = int(stdin.readline())
L = int(stdin.readline())
NET = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(L):
  x, y = map(int,stdin.readline().split())
  NET[y][x] = x
  NET[x][y] = y
D = deque([1]) # 출발 컴퓨터 1
visited = [False, False] + [True for _ in range(N-1)]
count = 0
while D:
  cur = D.popleft() # 현재 PC
  for num in NET[cur]: # 현재 PC에 연결된 다른 PC
    if num and visited[num]: # 현재 PC에 연결된 다른 PC가 count 되지 않았다면
      D.append(num) # 다른 PC 번호 Deque에 추가
      visited[num] = False # count 처리
      count += 1 # count값 증가
print(count)