백준 2606 바이러스

1번 컴퓨터를 루트로 하여 BFS탐색을 하면서 처음 방문하는 노드의 갯수를 새면 끝

adj 배열을 만들때 머가 가장 빠르고 메모리도 적당할까~ 생각해봤는데,

배열은 벡터가 아닌 2차원 배열을 쓰고 각 노드별로 연결된 링크의 갯수를 미리 저장하면 

adj의 자료구조로 링크드리스트를 쓸때의 장점과 배열을 쓸때의 장점을 둘 다 가져올거 같아서

이렇게 활용해 보았다.

괜찮은듯.

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <string>


using namespace std;

int adj[101][101];
int adjSize[101];
int computerNum;
int linkNum;
bool isVisit[101];

int main() {
	cin >> computerNum;
	cin >> linkNum;
	
	int from, to;

	for (int i = 0; i < 101; i++) {
		adjSize[i] = -1;
		isVisit[i] = false;
	}

	for (int i = 0; i < linkNum; i++) {
		cin >> from >> to;
		from--;
		to--;	
		adjSize[from]++;
		adj[from][adjSize[from]] = to;
		adjSize[to]++;
		adj[to][adjSize[to]] = from;
	}

	queue bfs;
	int result = 0;

	bfs.push(0);
	isVisit[0] = true;
	bfs.push(-1);

	while (true) {
		int now = bfs.front();
		bfs.pop();
		if (now == -1) {
			if (bfs.empty()) break;
			bfs.push(-1);
			continue;
		}
		int next;
		for (int r = 0; r <= adjSize[now]; r++) {
			next = adj[now][r];
			if (isVisit[next] == false) {
				bfs.push(next);
				isVisit[next] = true;
				result++;
			}
		}
	}

	cout << result << endl;

	return 0;
}