[BOJ] #2606 - 바이러스

2606번: 바이러스

 

 

** 문제 유형

• DFS, BFS

 

** 풀이

1. 단순히 시작 정점에서부터 도달할 수 있는 노드의 수를 계산하는 문제
2. DFS or BFS를 이용하여 방문하게 되는 노드의 개수를 계산
3. 컴퓨터의 수가 적으므로, DFS를 이용해 빠르게 문제를 푸는 것이 유리

 

def dfs(now_pos):
    global count
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
        if not visited[next_pos]:
            count += 1
            dfs(next_pos)

---

n = int(input())
m = int(input())

adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

dfs(1)
print(count)