[백준] 2606 바이러스 Python

[백준] 2606 바이러스 Python

쉽게 말하면 bfs 혹은 dfs를 실행해서 지나가는 노드 수를 count하면 된다.

from collections import deque
import sys
sys.stdin=open("input.txt")

n=int(input()) #컴퓨터 수
m=int(input()) #연결되어 있는 쌍의 수
graph=[[]for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited=[False for _ in range(n+1)]

def bfs(graph,visited,v):
    cnt=0
    q=deque()
    q.append(v)
    visited[v]=True

    while q:
        x=q.popleft()

        for i in graph[x]:
            if not visited[i]:
                visited[i]=True
                q.append(i)
                cnt+=1

    return cnt





print(bfs(graph,visited,1)) #1번 컴퓨터와 이어진 컴퓨터 cnt