[백준] 2606번:바이러스 (python 파이썬)

www.acmicpc.net/problem/2606

관련 알고리즘

나는 BFS를 이용해 풀었다.

BFS(Breath First Search)

출처 : https://towardsdatascience.com/10-graph-algorithms-visually-explained-e57faa1336f3

이처럼 인접한 노드를 먼저 탐색한다.

 

 

소스코드

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)