[백준] 2606 바이러스 c++ 구현

 

목차

 

 

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

 

2606번: 바이러스

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향 및 설명

큐를 이용하여 인접리스트로 bfs를 구현해 보았다.

알고리즘은 아래와 같다.

 

1번 노드 방문

 

 

 

 

 

1

 

 

1번 노드를 큐에서 제거하고 인접한 2번, 5번 노드 추가

 

 

 

 

 

2

5

 

 

2번 노드를 빼주고 인접한 3번 노드 추가

 

 

 

 

 

5

3

 

 

5번 노드를 빼주고 인접한 6번 노드 추가

 

 

 

 

 

 

3

6

 

 

인접한 노드가 없으므로 빼주기만 함

 

 

 

 

 

 

6

 

 

인접한 노드가 없으므로 빼주기만 함

 

 

 

 

 

 

 

 

큐가 비었으므로 bfs종료

 

 

코드 구현

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

//연결리스트로 구현한 bfs
vector<int> list[1000];    //vector를 배열로 만들어 주면 무방향 그래프를 구현할 수 있다.
bool visit[1000];  //방문한 노드 표시용 배열
int cnt = 0;  //전파된 컴퓨터를 세주기 위한 cnt


void bfs(int start) {
	queue<int> q;   // 큐에 넣고 visit을 true로 만들고 시작한다.
	q.push(start);
	visit[start] = true;
	
	while (!q.empty()) {  //큐가 빌때까지 반복해 준다.
		int x = q.front();
		q.pop();

		for (int i = 0; i < list[x].size(); i++) {
			int y = list[x][i];
			if (!visit[y]) {
				visit[y] = true;  //방문했다면 true로 만들어 준다.
				q.push(y);   //그리고 큐에 넣어준다.
			}
		
		}
		
	}

	for (int i = 0; i < sizeof(visit) / sizeof(visit[0]); i++) {   //방문한 곳의 개수를 세어준다.
		if (visit[i]) {
			cnt++;
		}
	}
	cout << cnt-1;   //1번 컴퓨터를 제외하고 전파된 컴퓨터의 개수

}


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

	int num, info, i, u, v;
	cin >> num;
	cin >> info;

	for (i = 0; i < info; i++) {
		cin >> u >> v;
		list[u].push_back(v);
		list[v].push_back(u);
	}

	bfs(1);  //1번 컴퓨터부터 시작


	
  
}