[백준 BOJ][C++]2606번 바이러스 풀이: BFS/DFS

 

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

2606번: 바이러스

 

 첫 번째 입력은 그래프의 노드 수, 두 번째 입력은 그래프의 엣지 수를 의미합니다.

 

 그 다음 입력으로 엣지 수 만큼의 연결된 두 노드가 주어집니다. 

 

 처음 문제를 접했을 때, 엣지 정보를 저장하는 2차원 배열을 선언하고 이를 바탕으로 인접리스트로 전체 그래프를 만들었으나 틀렸습니다 ㅠㅠ 아마 시간이 너무 걸린듯 합니다. 

 

 때문에 두 노드 u, v 입력이 주어지면 그래프 g[u][v]와 g[v][u]를 1로 설정하는 작업을 해주었습니다. 이는 두 노드 u, v가 연결되었음을 의미합니다. 

 

 이제 BFS나 DFS로 문제를 해결하면 됩니다!

 

 저는 BFS를 이용하였습니다. 

 

 Queue의 front 노드를 pop하여 그 노드와 연결된 모든 노드를 검사하여 아직 방문하지 않았다면 queue에 push 하고 방문 표시를 합니다. 이 작업을 queue가 empty일 때까지 반복하면 깔끔하게 풀립니다:)

 

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

using namespace std;

int n;
int e;
int visit[101] = { 0, };
int ans = 0;
int g[101][101];

void bfs() {

	queue<int> open_list;

	open_list.push(1);
	visit[1] = 1;

	while (!open_list.empty()) {
		int temp = open_list.front();
		open_list.pop();
		ans++;

		for (int i = 1; i <= n; i++) {
			if (g[temp][i] == 1 && visit[i] == 0) {
				visit[i] = 1;
				open_list.push(i);
			}
		}
	}

}

int main(void) {

	int u, v;

	cin >> n >> e;

	for (int i = 1; i <= e; i++) {
		cin >> u >> v;
		g[u][v] = g[v][u] = 1;

	}

	bfs();
	cout << ans - 1;

	return 0;
}