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

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2,3,5,6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 떄문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

 

출력

 

예제 입력

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력

4

 

풀이

 

 

//DFS 버전

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int N, M, cnt = 0;
vector<int> Graph[101];
bool visit[101] = { 0, };

void dfs(int v)
{
	visit[v] = true;

	for (int t = 0; t < Graph[v].size(); t++)
	{
		int k = Graph[v][t];
		if (!visit[k]) {
			cnt++;
			dfs(k);
		}
	}
	return;
}

int main()
{
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		Graph[x].push_back(y);
		Graph[x].push_back(x);
	}
	dfs(1);
	cout << cnt<<'\n';

	return 0;
}

---

BFS 버전은 가장 가까운 노드부터 Queue를 이용하여 

Graph[101][101]

	1	2	3	4	5	6	7
1	0	1	0	0	1	0	0
2	1	0	1	0	1	0	0
3	0	1	0	0	0	0	0
4	0	0	0	0	0	0	1
5	0	0	0	0	0	1	0
6	0	0	0	0	1	0	0
7	0		0	1	0	0	0

q 순서

 

//BFS 버전

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

int Graph[101][101];
bool visit[101] = { 0, };
queue<int> q;
int N = 0;//컴퓨터의 수
int M = 0;//네트워크 상 연결된 수
int cnt = 0;

void bfs(int s)
{
	q.push(s); //노드 시작 1 넣기
	visit[s] = true;

	while (!q.empty()) //큐에 노드 없을 때까지
	{
		s = q.front();
		q.pop();

		for (int i = 1; i <= N; i++) {
			if (Graph[s][i] == 1 && visit[i] == 0) // 경로가 있는데 방문하지 않았을 경우
			{
				q.push(i);
				visit[i] = true;
				cnt++;
			}
		}
	}
}

int main(int argc, char** argv)
{
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int x = 0;
		int y = 0;
		cin >> x >> y;
		Graph[x][y] = 1;//노드 서로 
		Graph[y][x] = 1;//연결 되어 있음 양방향이라는 소리
	}
	
	bfs(1);
	cout << cnt << endl;

	return 0;
}

 

---

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