백준 2606번 - 바이러스 (C++/BFS/Graph)

문제

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

2606번: 바이러스

접근법

간단한 BFS문제이다. 오랜만에 adjacants를 쓰는 문제가 나와 기분이 좋았다. (그동안은 배열에서 +- 1하면서 하느라 귀찮았다...)

BFS를 시작점을 1로 해서 visited가 1로바뀌는 순간마다 cnt를 ++ 해주면 된다.

다만 자기자신은 빼야하므로, 마지막 출력때 -1을 해주었다.

BFS개념을 알고있으면 얼마 걸리지 않을 문제이다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int cnt = 0;
void BFS(vector<vector<int>>& adjacants, vector<int>& visited)
{
	queue<int> q;
	q.push(1);
	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		if (visited[here] != 1)
		{
			visited[here] = 1;
			for (int i : adjacants[here])
				q.push(i);
			cnt++;
		}
	}
}

int main()
{
	int N, M;
	cin >> N;
	cin >> M;
	vector<vector<int>> adjacants(N + 1);
	vector<int> visited(N + 1,0);

	for (int i = 0; i < M; i++)
	{
		int from, to;
		cin >> from >> to;
		adjacants[from].push_back(to);
		adjacants[to].push_back(from);
	}
	BFS(adjacants,visited);
	cout << cnt - 1;
}