[Baekjoon] - 2606. ウイルス(S 3)
1. Problem 📃
📚 ソース-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行目に出力する.
I/O例
サンプル入力サンプル出力7612355256474
2. Logic 👨🏫
典型的なBFS問題は、今はもう慣れました!!
Logic 1. BFS
1.queue(deque)の作成
2.queueに開始ノードを配置し、アクセスノードを確認する
3.キューが要求されるまで繰り返す
4.queueから要素を取り出す
5.まだアクセスしていない隣接ノードがある場合は、キューを挿入します.
3. Code 💻
1.参照解読コード😁
from collections import deque
def bfs(k):
q = deque()
q.append(k)
visited[k] = 1
cnt = 0
while q:
v = q.popleft()
for i in range(1, n+1):
if graph[v][i] == 1 and visited[i] == 0:
cnt += 1
visited[i] = 1
q.append(i)
return cnt
n = int(input())
m = int(input())
graph = [[0] * (n+1) for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
visited = [0] * (n+1)
print(bfs(1))
参考資料📩
私のBFSクリアランス
Reference
この問題について([Baekjoon] - 2606. ウイルス(S 3)), 我々は、より多くの情報をここで見つけました
https://velog.io/@odh0112/Baekjoon-2606.-바이러스S3
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
典型的なBFS問題は、今はもう慣れました!!
Logic 1. BFS
1.queue(deque)の作成
2.queueに開始ノードを配置し、アクセスノードを確認する
3.キューが要求されるまで繰り返す
4.queueから要素を取り出す
5.まだアクセスしていない隣接ノードがある場合は、キューを挿入します.
3. Code 💻
1.参照解読コード😁
from collections import deque
def bfs(k):
q = deque()
q.append(k)
visited[k] = 1
cnt = 0
while q:
v = q.popleft()
for i in range(1, n+1):
if graph[v][i] == 1 and visited[i] == 0:
cnt += 1
visited[i] = 1
q.append(i)
return cnt
n = int(input())
m = int(input())
graph = [[0] * (n+1) for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
visited = [0] * (n+1)
print(bfs(1))
参考資料📩
私のBFSクリアランス
Reference
この問題について([Baekjoon] - 2606. ウイルス(S 3)), 我々は、より多くの情報をここで見つけました
https://velog.io/@odh0112/Baekjoon-2606.-바이러스S3
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
from collections import deque
def bfs(k):
q = deque()
q.append(k)
visited[k] = 1
cnt = 0
while q:
v = q.popleft()
for i in range(1, n+1):
if graph[v][i] == 1 and visited[i] == 0:
cnt += 1
visited[i] = 1
q.append(i)
return cnt
n = int(input())
m = int(input())
graph = [[0] * (n+1) for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
visited = [0] * (n+1)
print(bfs(1))
Reference
この問題について([Baekjoon] - 2606. ウイルス(S 3)), 我々は、より多くの情報をここで見つけました https://velog.io/@odh0112/Baekjoon-2606.-바이러스S3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol