[백준 알고리즘 c++] 문제 36.바이러스 2606

알고리즘

 

[문제]

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

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

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

 

[나의 풀이]

 

//문제
1. 1번 컴퓨터가 바이러스 걸렸을때 웜 바이러스가 걸리는 컴퓨터의 수를 출력하시오. (bfs로 풀고 dfs로 풀기)
입력
1. 총 컴퓨터 수(정점) N을 입력 받는다.
2. 간선의 갯수 M을 입력 받는다.
3. M갯수만큼 반복문을 돌리며 간선을 이어준다.
처리
4. 정점의 수를 정렬해준다.
출력
1. 정렬된 정점의 첫 번째로부터 몇개가 카운트되는지 출력한다.

[소스 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <stack>


using namespace std;

//vector를 배열대신 사용
vector<int> graph[101];

int bfs()
{
	int count = 0;

	//방문 여부를 담아줄 배열을 선언한다.
	bool isVisited[101] = { false };

	//큐로 구현
	queue<int> que;
	que.push(1);
	isVisited[1] = true;
	
	while (!que.empty())
	{
		
		int node = que.front();
		que.pop();

		for (int nextNode : graph[node])
		{
			if (isVisited[nextNode] == false)
			{
				que.push(nextNode);
				isVisited[nextNode] = true;
				count++;
			}
		}
	}

	return count;

}


int dfs()
{
	int count = 0;

	//방문 여부를 담아줄 배열을 선언한다.
	bool isVisited[101] = {false};

	//stack로 구현
	stack<int> st;

	//1번 컴퓨터에서 시작
	st.push(1);
	isVisited[1] = true;

	while (!st.empty())
	{
		int node = st.top();
		if (isVisited[node] == false)
		{
			isVisited[node] = true;
			count++;
		}
		st.pop();
		
		for (int newNode : graph[node])
		{
			if (isVisited[newNode] == false)
			{
				st.push(newNode);
			}
		}
	}


	return count;
}

int main()
{

	//문제
	// 1. 1번 컴퓨터가 바이러스 걸렸을때 웜 바이러스가 걸리는 컴퓨터의 수를 출력하시오. (bfs로 풀고 dfs로 풀기)
	// 입력
	// 1. 총 컴퓨터 수(정점) N을 입력 받는다.
	// 2. 간선의 갯수 M을 입력 받는다.
	// 3. M갯수만큼 반복문을 돌리며 간선을 이어준다.
	// 처리
	// 4. 정점의 수를 정렬해준다.
	// 출력
	// 1. 정렬된 정점의 첫 번째로부터 몇개가 카운트되는지 출력한다.

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N = 0;
	int M = 0;
	
	cin >> N >> M;

	//간선을 이저주는 인접리스트 방식을 사용
	for (int i = 0; i < M; i++)
	{
		int node, node2;
		cin >> node >> node2;

		graph[node].push_back(node2);
		graph[node2].push_back(node);
	}
	

	for (int i = 1; i <= N; i++)
	{
		sort(graph[i].begin(), graph[i].end());
	}

	//cout << bfs();

	for (int i = 1; i <= N; i++)
	{
		sort(graph[i].rbegin(), graph[i].rend());
	}

	cout << dfs();


	return 0;
}

 

[피드백]