[백준/python] 2606번 바이러스

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

2606번: 바이러스

 

문제분석

한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다.

 

코드

def bfs(x):
    q = deque(); q.append(x)
    while q:
        x = q.popleft()
        for i in arr[x]:
            if visit[i] == 0:
                q.append(i)
                visit[i] = 1

    return sum(visit) - 1

from collections import deque

n = int(input())
m = int(input())
arr = [[] for _ in range(n + 1)]
visit = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

print(bfs(1))

 

문제풀이

1. 컴퓨터의 수는 n에 연결되어 있는 컴퓨터 쌍의 수는 m에 저장한다.

2. 컴퓨터의 네트워크 연결관계를 저장할 arr와 방문 여부를 저장할 visit를 만든다.

3. for문을 통해 컴퓨터의 번호 쌍을 입력받아 arr에 연결되어있는 컴퓨터의 관계를 저장한다.

4. 문제는 1번 컴퓨터가 바이러스에 걸렸다고 가정하기 때문에, bfs(1)로 시작한다.

5. bfs는 deque()를 사용하여 정의한다.

6. queue의 왼쪽 값(= 바이러스에 걸린 컴퓨터 번호)을 pop 해서 x에 저장한다.

7. 컴퓨터의 연결관계가 저장되어있는 arr을 통해서 x컴퓨터 때문에 바이러스에 옮은 컴퓨터를 q에 저장하고, 방문했다는 표시를 한다. 계속해서 새롭게 바이러스에 옮은 컴퓨터 때문에 바이러스에 감염된 컴퓨터를 찾아낸다.

8. queue가 끝날 때까지 반복한 뒤, 바이러스에 걸리게 되는 컴퓨터의 수를 return 해준다.