2606번 : 바이러스

https://www.acmicpc.net/problem/2606

 

 

감염을 '연결된 노드 탐색'으로 해석하여 BFS로 풀이했다.

# https://www.acmicpc.net/problem/2606
# BFS

import sys
from collections import defaultdict, deque

num_com = int(input())
num_edges = int(input())

graph = defaultdict(list)
for _ in range(num_edges) :
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def BFS(graph) :
    visited = [0 for _ in range(num_com)]
    visited[0] = 1
    q = deque([1])
    while q :
        u = q.popleft()
        for v in graph[u] :
            if visited[v-1] == 0 :
                visited[v-1] = 1
                q.append(v)
    
    ans = sum(visited) - 1
    print(ans)

BFS(graph)

 

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력해야 하므로, visited에서 방문(감염)한 노드에 1을 표시하고 마지막에 visted 내 원소의 합을 구했다.

'1번 컴퓨터를 통해' 감염된 컴퓨터 수는 1번 컴퓨터를 제외해야 하기에 1을 뺀 값으로 정답을 구했다.