백준 2606 바이러스(c++)

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

2606번: 바이러스

bfs

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define max 101
using namespace std;
int n, com;
int cnt=0;
int graph[max][max];
void bfs(int node){
	bool visited[max]= {false};
	
	queue<int>myqueue;
	visited[node]=true;
	myqueue.push(node);
	
	while(!myqueue.empty()){
		int curr = myqueue.front();
		myqueue.pop();
		for(int next = 1; next<=com;++next){
			if(!visited[next] && graph[curr][next]){
				visited[next] = true;
				myqueue.push(next);	
				cnt++;
		}
	}
	}
	cout<<cnt;
}
int main()
{
	cin>>com;
	cin>>n;
	memset(graph,0,sizeof(graph));
	for(int i=0;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		graph[u][v]=graph[v][u]=1;
	}
	bfs(1);
	return 0;
}

dfs

<코드>

#include <iostream>
#include <cstring>
using namespace std;
#define max 101
int n, e;
int graph[max][max];
bool visited[max];
int cnt=0;
void dfs(int node)
{
	visited[node] = true;
	//방문 노드 출력 
	for(int next=1;next<=n; next++)
	{
		//간선이 있고, 방문여부 확인(방문하지 않았을 때, 탐색진행) 
		if(!visited[next] && graph[node][next]){
			dfs(next);
			cnt++;
		}
	}
}
int main()
{
	cin>>n>>e;
	memset(visited, 0, sizeof(visited));
	memset(graph, 0, sizeof(graph));
	for(int i=0;i<e;i++)
	{
		int u,v;
		cin>>u>>v;
		graph[u][v]=graph[v][u]=1;
	}
	dfs(1);
	cout<<cnt;
	return 0;
}

<풀이과정>

1번 컴퓨터에 바이러스가 걸렸으므로, 1번 컴퓨터와 연결된 컴퓨터가 몇 개 있는지 확인해주면 된다.

우선, 1번 컴퓨터와 연결되어있는 노드 2,5(예시)를 각각 푸쉬해준다. 그리고 pop하면 선입선출 구조인 queue로 인해, 2가 빠져나오게 된다. 그리고 2와 연결된 요소를 찾으면 3이 있다. 3은 아무랑도 연결되어있지 않다. 다음 요소인 5를 보면, 5는 1,2,6이랑 연결되어있지만, 1과 2는 방문을 했기에 6만 방문하면 된다. 그래서 1과 연결된 총 노드 수는 2,3,5,6 4개가 된다. 4랑 7은 1과 연결되어있지 않기에 고려사항이 될 수 없다. (왜냐하면 curr라는 현재 요소에 존재하기 않기에, push, pop 하는 과정이 없기 때문이다)