[Python] 바이러스 - 백준 (BFS)

해당 글은 백준 2606번 문제 '바이러스'를 다룬다.

문제

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

2606번: 바이러스

 

설명

해당 문제는 DFS/BFS로 풀 수 있다. 해당 글은 BFS 알고리즘으로 해당 문제를 해결하였다.

입력에 맞게 graph를 구성해준 후, 출발점 1에서부터 연결된 모든 노드에게 방문하고,

방문된 횟수의 총합에서 출발점 1을 제외한 값(-1)을 출력해준다.

 

코드

from collections import deque

computers = int(input())
networks = int(input())
graph = [[] for _ in range(computers+1)]
visited = [0]*(computers+1)

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

def bfs(graph, start):
    queue = deque([start])
    visited[start] = 1

    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = 1
    return sum(visited)-1

print(bfs(graph, 1))