[BOJ] 2606 바이러스 C++

개요

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

2606번: 바이러스

실버 3급 그래프 탐색 문제다.

본문

풀이

그래프 탐색 문제 중 저 난이도 문제인듯하다.

제한이 크게 없어 BFS, DFS 중 어느 것을 사용해도 문제가 없을 것이라 판단했다.

queue를 활용한 인접 리스트(vector) 기반 BFS로 풀었다.

1번 컴퓨터는 제외이기 때문에 이 점에 유의해야 한다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
constexpr int RANGE = 102;

int bfs(vector<int>* g, int start) {
	int visited[RANGE]{};
	int cnt = 0;
	queue<int> q;
	q.push(start);

	while (!q.empty())
	{
		int nowV = q.front();
		q.pop();

		if (visited[nowV]) continue;
		visited[nowV] = true;
		cnt++;

		for (int i = 0; i < g[nowV].size(); i++)
			q.push(g[nowV][i]);
	}
	return cnt-1;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int v, e;
	vector<int> graph[RANGE]{};

	cin >> v >> e;

	for (int i = 1; i <= e; i++) {
		int from, to;
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	int cnt = bfs(graph, 1);
	cout << cnt;
}