[Python 3] BOJ - 2606 "바이러스"

 # 문제 링크 : https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

 # 풀이 :

이 문제는 단순히 양방향 BFS를 1번 정점에서 실행시키면 된다.

 

 # 코드 

import sys, collections

# 인접 리스트 생성 및 입력부
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
adj = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
    
bfs : bfs를 통해 1번 컴퓨터를 통해 감염된 컴퓨터의 수를 리턴하는 함수
def bfs(v):
    q = collections.deque()
    check = [False] * n
    check[v] = True
    q.append(v)
    while q:
        now = q.popleft()
        for i in adj[now]:
            if check[i] == False:
                check[i] = True
                q.append(i)
    cnt = 0
    for i in check:
        if i == True:
            cnt += 1
    return cnt - 1

print(bfs(0))