2606번. 바이러스

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

 

 

 

BFS 혹은 DFS로 풀 수 있는 문제인데, 전에 포스팅했던 문제보다는 조건이 덜 까다롭다.

인접 노드들을 일정한 순서대로 방문할 필요가 없으므로 인접 노드들을 저장할 때 set을 사용했다.

 

import sys
import collections


def BFS(start):
    infected = []
    queue = collections.deque()
    queue.append(start)

    while queue:
        node = queue.popleft()
        if node not in infected:
            infected.append(node)
            if node in network:
                queue.extend(network[node])
    return len(infected)-1


nodeCount = int(sys.stdin.readline())
edgeCount = int(sys.stdin.readline())
network = {}

for _ in range(edgeCount):
    start, end = map(int, sys.stdin.readline().split())
    if start not in network:
        network[start] = {end}  # set. 집합
    elif start in network:
        network[start].add(end)
    if end not in network:
        network[end] = {start}
    elif end in network:
        network[end].add(start)

#print(network)

print(BFS(1))