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

1. 문제 링크

www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

 

2. 문제 설명

컴퓨터(정점)의 수, 연결되어 있는 컴퓨터 쌍(간선)의 수, 연결되어 있는 컴퓨터의 번호 쌍(간선이 연결하는 두 정점의 번호)를 입력받아서

1번 컴퓨터(정점)에 연결되어 있는 컴퓨터의 수(정점의 수)를 출력하는 문제입니다.

 

 

 

3. 소스코드

BOJ 2606번 바이러스 C++ 풀이입니다.

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

vector<int> e[101];
bool check[101];

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

	int cn, pn, from, to, cnt = 0;
	queue<int> q;
	cin >> cn >> pn;
	for (int i = 0; i < pn; i++) {
		cin >> from >> to;
		e[from].push_back(to);
		e[to].push_back(from);
	}

	q.push(1);
	check[1] = true;
	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < e[cur].size(); i++) {
			int next = e[cur][i];
			if (!check[next]) {
				check[next] = true;
				q.push(next);
				cnt++;
			}
		}
	}
	cout << cnt;

	return 0;
}

6번 라인 : 인접 리스트를 저장할 vector를 정점의 최대 개수가 100이므로 e[100]으로 접근할 수 있도록 101의 크기로 선언했습니다.

7번 라인 : 정점의 방문을 체크할 배열 check도 마찬가지 이유로 101의 크기로 선언했습니다.

15번 라인 : 컴퓨터의 개수를 cn, 컴퓨터 쌍의 수를 pn에 저장합니다.

16 ~ 20번 라인 : 컴퓨터는 서로 연결되어 있으므로 인접 리스트에 양방향으로 저장합니다.

22번 라인 : 1번 컴퓨터를 방문하기 위해 q에 1을 push하고,

23번 라인 : check[1]을 true로 변경하면서 방문한 것을 표시합니다.

24번 라인 : q가 비어있지 않는 동안

25번 라인 : cur변수에 현재 방문한 정점을 q.front()를 이용하여 저장하고,

26번 라인 : q.pop()을 이용하여 q에서 빼주고,

27번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,

28번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,

29번 라인 : next정점을 방문한 적이 없으면(check[next] == false)

30번 라인 : next정점을 방문하였다고 표시한 후(check[next] = true)

31번 라인 : q에 next정점을 push하고

32번 라인 : 1번 컴퓨터와 연결된 컴퓨터의 개수(cnt)를 1 증가시킵니다.

36번 라인 : 최종 결과(cnt)를 출력합니다.