[백준][C++] 2606번 바이러스

2606번 바이러스

문제 링크

바이러스

분석

한 네트워크에는 N개의 컴퓨터가 연결되어 있습니다.
1번 컴퓨터가 바이러스에 감염되었을 때, 연결된 컴퓨터에서 네트워크를 통해 바이러스가 퍼지게 됩니다.
이때, 1번 컴퓨터를 제외한 감염된 컴퓨터의 수를 구해야합니다.

그래프를 통해 컴퓨터들끼리 연결된 네트워크를 표현할 수 있습니다.
해당 문제에서는 양방향 연결이고, 가중치가 없습니다.

그래프의 탐색은 DFS또는 BFS를 사용하면 됩니다.
1번에서 고정적으로 출발하여 방문할 수 있는 모든 정점을 탐색하면 됩니다.

풀이

#include <iostream>
#include <vector>

int answer = 0;

void dfs(const std::vector<std::vector<int>>& graph, std::vector<bool>& visited, int index)
{
	visited[index] = true;

	for (int next : graph[index])
	{
		if (!visited[next])
		{
			++answer;
			dfs(graph, visited, next);
		}
	}
}

int main()
{
	int computerCount, pairCount;
	std::cin >> computerCount >> pairCount;

	std::vector<std::vector<int>> graph(computerCount + 1);

	for (int i = 0; i < pairCount; ++i)
	{
		int computerA, computerB;

		std::cin >> computerA >> computerB;

		graph[computerA].push_back(computerB);
		graph[computerB].push_back(computerA);
	}

	std::vector<bool> visited(computerCount + 1);

	dfs(graph, visited, 1);

	std::cout << answer << std::endl;
}

성능 요약

시간 복잡도는

• 그래프를 생성하며, 연결된 간선을 저장하는 반복문 $O(m)$
  • m은 주어진 간선의 개수를 의미
• DFS 탐색 $O(n + m)$
  • n은 주어진 정점의 개수를 의미

공간 복잡도는

• 그래프를 저장하는 std::vector<std::vector<int>> graph $O(n + m)$
• 방문 여부를 저장하는 std::vector<bool> visited $O(n)$
• 재귀 호출 스택 $O(n)$

메모리: 2020 KB

시간: 0 ms