[백준/C++] 바이러스_2606

📝 문제

https://www.acmicpc.net/problem/2606
양방향 그래프로 dfs와 bfs로 풀어보았다.

💻 코드

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

using namespace std;

int n; // 컴퓨터의 수
int node;	//  컴퓨터 쌍 개수
int check[101] = { 0, };
vector<int> com[101];
int answer = 0;
queue<int> q;

void dfs(int start) {
	
	for (int i = 0; i < com[start].size(); i++) {
		int next = com[start][i];
		if (check[next]) continue;
		check[next] = 1;
		answer += 1;
		dfs(next);
	}
}

void bfs() {

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 0; i < com[now].size(); i++) {
			int next = com[now][i];
			if (check[next]) continue;
			answer += 1;
			check[next] = 1;
			q.push(next);
		}
	}
	
}

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

	for (int i = 0; i < node; i++) {
		int start, end;
		cin >> start >> end;
		com[start].push_back(end);
		com[end].push_back(start);
	}	// 인접 리스트로 컴퓨터 관계 구현

	// dfs로 카운트 하기
	check[1] = 1;
	dfs(1);

	// bfs로 카운트 하기
	check[1] = 1;
	q.push(1);
	bfs();

	cout << answer;

	return 0;
}

💡 Point

배열의 크기를 미리 최대치를 사용해서 메모리가 낭비되는 것 같다.
입력 n에 맞는 배열 선언 방법을 학습해야 될듯,,,