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

 

오늘도 dfs/bfs 문제~~

 

문제 2606번

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

2606번: 바이러스

 

이 문제는 dfs나 bfs로 풀면 되는 문제인데, 나는 그냥 bfs로 접근해 count를 1씩 증가시켜가며 문제를 해결하였다.

어제 공부해놔서 그런지 쉽게 풀렸다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

bool visited[1001];
vector<int> node[1001];

void bfs(int start) {
	int count = 0;
	queue<int> q;

	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < node[x].size(); i++) {
			int y = node[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
				count++;
			}
		}
	}
	cout << count << '\n';
}


int main() {
	int n, m, k, w;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> k >> w;
		node[k].push_back(w);
		node[w].push_back(k);
	}
	for (int i = 1; i <= n; i++) {
		sort(node[i].begin(), node[i].end());
	}
	bfs(1);
}