[알고리즘] 백준 2606 바이러스 - 파이썬

오늘도 백준의 단계별 풀기에서 DFS, BFS에 관한 문제를 풀어보았습니다. 

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

2606번: 바이러스

 

from collections import deque
from sys import stdin

n = int(input()) # 컴퓨터의 수
m = int(input()) # 연결된 수


graph = [[0] * (n+1) for _ in range(n+1)] # 인접행렬 생성

for _ in range(m):
    x, y = map(int, stdin.readline().split())
    graph[x][y] = 1
    graph[y][x] = 1

visited = [False] * (n+1) # 감염여부에 대한 리스트 생성 

def bfs(graph, v):
    count = 0  # 감염된 컴퓨터의 수
    queue = deque([v])
    visited[v] = True # 감염이 되면 True

    while queue:
        v = queue.popleft() 
        count += 1 # pop을 해줄때마다 카운트
        for i in range(len(graph[v])):
            if graph[v][i] == 1 and visited[i] == False:
                queue.append(i)
                visited[i] = True
    return count-1 # 처음 1을 제외

print(bfs(graph, 1))

 

문제풀이 : 이번 바이러스 문제는 전에 풀었던 BFS문제와 매우 유사해서 풀기 쉬웠던 문제입니다. 지문에서 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜바이러스에 걸린다는 부분에서 deque를 활용하는 bfs풀이를 적용해야한다고 생각했습니다. 코드에서 count변수를 두어 queue에서 하나씩 뺄때마다 +1을 해주었고 리턴할때는 첫번쨰 컴퓨터를 제외하였습니다.