BOJ 2606 - 바이러스

풀이

---

정점 a 와 b 에 대한 m 개의 간선 정보를 정수로 입력받고 이를 인접행렬로 저장해준다.

n 개의 컴퓨터에 대하여 방문처리를 위한 visited 리스트를 선언한 뒤 1번 컴퓨터를 시작으로 BFS 를 통해 실행시켜준다.

1번 컴퓨터와 인접한 모든 컴퓨터에 관하여 BFS 가 실행될 때 ans 리스트에 인접한 컴퓨터들을 모두 반환한다.

이후 출력조건에 맞춰서 1과 연결된 컴퓨터를 출력해주면된다.

소스코드

---

# 바이러스
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(v):
    ans = []
    q = deque()
    q.append(v)
    visited[v] = 1
    while q:
        v = q.popleft()
        ans.append(v)
        for i in range(1, n+1):
            if visited[i] == 0 and graph[v][i] == 1:
                q.append(i)
                visited[i] = 1
    return ans
 
n = int(input())
m = int(input())
 
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [0] * (n+1)
 
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1
 
ans = bfs(1)
ans.remove(1)
print(len(ans))

References

---

• BOJ 2606 - 바이러스