[C++] 백준 2606번 - 바이러스

[C++] 백준 2606번 - 바이러스

dfs로 간단하게 풀 수 있는 문제이다.

1번 컴퓨터를 통해 감염되는 컴퓨터의 개수를 출력하면 되기 때문에,

탐색을 할 노드를 1번 노드로 고정을 해놓고,

1번 노드를 통해 다시 재귀로 탐색을 할 때마다 감염된 컴퓨터의 수를 하나씩 증가시켜주면 된다.

#include #include #include #include #include using namespace std; vector a[1001]; bool check[1001]; int infected = 0; void dfs(int node) { check[node] = true; for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { infected += 1; dfs(next); } } } void bfs(int start) { queue q; memset(check, false, sizeof(check)); check[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); printf("%d ", node); for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { check[next] = true; q.push(next); } } } } int main() { int n, m; cin >> n; cin >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } for (int i = 1; i <= n; i++) { sort(a[i].begin(), a[i].end()); } dfs(1); cout << infected << "

"; return 0; }

from http://littlejay.tistory.com/108 by ccl(A) rewrite - 2021-08-19 16:00:28