[BOJ] 2606번 : 바이러스

1. 문제

2606번: 바이러스

1. 인접 바이러스가 모두 감염
2. 1번 정점이 바이러스일 때 감염되는 컴퓨터(정점) 수

2. 알고리즘

1. dfs
2. 그래프 탐색 후 방문한 정점 개수 - 1 출력
3. 1번 컴퓨터를 통해 감염된 컴퓨터 수이므로 1번 컴퓨터 제외

3. 소스코드

# graph 저장을 위한 defaultdict
from collections import defaultdict
n = int(input())
k = int(input())

graph = defaultdict(list)
visited = set() # 방문 정점 기록

for _ in range(k):
    u, v = map(int, input().split())
    graph[u].append(v) # u, v 정점 연결
    graph[v].append(u) 
    
def dfs(v):
    visited.add(v)
    
    for i in graph[v]:
        if i not in visited:
            dfs(i)

dfs(1) # 1번 컴퓨터 부터 감염(그래프 탐색)
print(len(visited) - 1) # 1번 제외 방문 정점 개수 출력