백준(BAEKJOOB) 2606번 바이러스 // c++언어

문제

---

나는 이문제를  커피 우선 방식인 BFS로 풀기로 했다.

 

Int n, m;
//n은 노드의 개수
//m간선의 개수

int vis[10000];
vector<int>map[101]; //인접한다는 것을 알려 주기위해서 vector로 선언

 

map을 vector로 선언한 이유는 밑에 인접한 숫자들을 표현해 줄 때 일반

int 형을 써버리면 쓸 수 없게 되어서 vector를 이용하였습니다.

 

 

 

기본 bfs 구조를 쓰고

거기서 pop을 한 후 count 숫자가 하나씩 카운터 하게 

만들었습니다.

(연결되어있는 컴퓨터만 숫자를 카운터 해야 되기 때문에)

while (!queue.empty()) {
		int x = queue.front();
		queue.pop();
		coun++; 
		//숫자가 있을경우
		// 큐에 맨앞에 있는 숫자를 x라 하고
		// pop 해준후 count 해준다.
		for (int i = 0; i < map[x].size(); i++) {
			int y = map[x][i];
			if (!vis[y]) {
				queue.push(y);
				vis[y] = true;

			} //인접한 친구들 방문처리

		}
	}
}

 

 

 

map [a]. push_back(b);
map [b]. push_back(a);

두 그래프를 서로 연결시킵니다

 

bfs에 1을 준 이유는 start에 1부터 시작하기 위해서입니다

문제를 잘 읽어보면 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 를

이야기하고 있기 때문에

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}

	bfs(1);
	cout << coun << endl;

}

 

 

 

 

 

 

 

총 코드

 

 

 

 

 

---

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int n, m;
//n은 노드의 개수
//m간선의 갯수

int vis[10000];
vector<int>map[101]; //인접한다는 것을 알려 주기위해서 vector로 선언

int coun = -1;
//-1인 이유는 : 자기자신 1을 포함하니 1부터시작해서 -1을 count로 해줬다

void bfs(int start) {
	queue<int>queue;
	queue.push(start); // start를 큐에 가장 앞쪽에 넣어준다.
	vis[start] = true; // start 방문처리 

	while (!queue.empty()) {
		int x = queue.front();
		queue.pop();
		coun++; 
		//숫자가 있을경우
		// 큐에 맨앞에 있는 숫자를 x라 하고
		// pop 해준후 count 해준다.
		for (int i = 0; i < map[x].size(); i++) {
			int y = map[x][i];
			if (!vis[y]) {
				queue.push(y);
				vis[y] = true;

			} //인접한 친구들 방문처리

		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}

	bfs(1);
	cout << coun << endl;

}