Coding - Algo/python
[백준] 2606번:바이러스 (python 파이썬)
jainn
2021. 1. 3. 00:32
728x90
관련 알고리즘
나는 BFS를 이용해 풀었다.
BFS(Breath First Search)
이처럼 인접한 노드를 먼저 탐색한다.
소스코드
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
arr = list([0]*(n) for i in range(n))
visit = list([0]*(n))
def bfs(x):
que = [x]
while que:
now = que.pop(0)
for i in range(n):
if arr[now][i] == 1 and visit[i] == 0:
visit[i]=1
que.append(i)
for i in range(m):
x, y = map(int, input().split())
arr[x-1][y-1] = arr[y-1][x-1] = 1
bfs(0)
print(sum(visit)-1)
반응형