백준: 2606 바이러스

문제

2606번: 바이러스

 

문제 풀이

 웜 바이러스가 하나의 네트워크 영역에서 퍼진다. 1번 컴퓨터부터 시작하여 웜 바이러스가 감염되는 컴퓨터의 개수를 반환하는 문제이다. 문제는 BFS/DFS 탐색을 통해 1번 노드로부터 탐색 가능한 영역을 찾는 문제이다. 초기에 입력되는 그래프의 정보를 양방향으로 기록하고 탐색을 진행하면 된다.

 

코드

from sys import stdin
from collections import defaultdict, deque


def bfs(start):
    q = deque([start])

    while q:
        cur_node = q.popleft()

        for next_node in graph[cur_node]:
            if next_node not in visited:
                visited.append(next_node)
                q.append(next_node)

    # 1번 컴퓨터를 제외한 다른 노드들.
    return len(visited) - 1


if __name__ == '__main__':
    n = int(stdin.readline())
    graph = defaultdict(set)
    visited = [1]

    for _ in range(int(stdin.readline())):
        node1, node2 = map(int, stdin.readline().split())
        graph[node1].add(node2)
        graph[node2].add(node1)

    print(bfs(1))